• Categories
• Teoría de la computación
• Áreas de la informática
• Métodos formales
• Modelos de computación
• Física y matemáticas

Citation preview

MODELAR PROBLEMAS DE LENGUAJES INDEPENDIENTES DEL CONTEXTO Unidad 2 – Fase 3: Actividad Intermedia

PRESENTADO POR: Jenny Zulema Monsalve Valencia – 43998519 John Andrés Jiménez Cano – 86081389 Ricardo Rodríguez – 0000000000 Hernando Trujillo – 80182348 Grupo – 301405_7

PRESENTADO A: JHEIMER JULIAN SEPULVEDA – TUTOR

UNIVERSIDAS ABIERTA Y A DISTANCIA – UNAD ESCUELA DE CIENCIAS BÁSICAS DE TECNOLOGÍA E INGENIERÍA AUTÓMATAS Y LENGUAJES FORMALES ABRIL 2019 BOGOTÁ

TABLA DE CONTENIDO

1.

2.

OBJETIVOS .................................................................................................................. 3 1.1.

OBJETIVO GENERAL ........................................................................................ 3

1.2.

OBJETIVOS ESPECÍFICOS ............................................................................... 3

DESARROLLO DE LA ACTIVIDAD ........................................................................ 4 2.1.

Describa la forma matemática el autómata ............ Error! Bookmark not defined.

2.2.

Plasmar la tabla de transición del autómata ........... Error! Bookmark not defined.

2.3. Identifique los elementos del autómata, describa cada elemento, la función y significado del autómata. .................................................. Error! Bookmark not defined. 2.4. Muestre en el simulador como recorre una cadena valida. Explique cada secuencia. ............................................................................................................................ 4 2.5. Muestre el diagrama de Moore generado en JFLAP y en VAS y comente tres similitudes y tres diferencias que encuentra al realizarlo en los dos simuladores. .... Error! Bookmark not defined. 3.

ANEXOS ........................................................................................................................ 6 3.1.

Conversión de un Autómata Finito a Expresión Regular. ....................................... 6

3.2. Conversión de Autómatas Finitos Deterministas a Autómatas Finitos No deterministas (AFD a AFND) y viceversa ........................ Error! Bookmark not defined. 4.

CONCLUSIONES ....................................................................................................... 10

5.

REFERENCIAS BIBLIOGRÁFICAS ...................................................................... 11

1. OBJETIVOS 1.1. 

OBJETIVO GENERAL

1.2.

Construir gramáticas y autómatas mediante los mecanismos de representación formal de los diferentes autómatas, comprendiendo el tipo de problemas que cada uno puede resolver. OBJETIVOS ESPECÍFICOS



Validar los aspectos que tienen la caracterización del autómata de pila y cómo una cadena recorre los diferentes estados que pueden tener. Además de realizar una diferenciación entre autómata de pila por estado final y autómata de pila por pila vacía.



Realizar el proceso de minimización del autómata, identificando sus componentes tales como su notación formal, su gramática y su lenguaje.



Utilizar uno de los simuladores ejecutar los autómatas (inicial y resultado) y validar por lo menos 5 cadenas aceptadas y 5 rechazadas cada una de 8 caracteres como mínimo.

2. DESARROLLO DE LA ACTIVIDAD 2.1.   

Realice el proceso paso a paso la minimización del autómata. Realice la notación formal (caracterización) matemática del autómata ya minimizado Identifique El Lenguaje que reconoce. Identifique su gramática (de forma manual) por la derecha y caracterícela. Debe incluir el diagrama de estados con los componentes de la gramática asociados a las variables y a las constantes.

EJERCICIO A TRABAJAR

Procedimiento de minimización

Realice de manera detallada el procedimiento paso a paso de la minimización del autómata. Paso 1 X={q2, q4, q8} Y={q0, q1, q3, q5, q6, q7} Paso 2 Aceptadore sX 0 q2 q4

X X

1 Y X

q8

Y

X

3. ANEXOS 3.1.

Autómata de Pila [Hernando Trujillo]

El diseño solicitado corresponde al diligenciamiento de la siguiente tabla:

3.2.

Autómata de Pila [John Jiménez]

El diseño solicitado corresponde al diligenciamiento de la siguiente tabla: EJERCICIO A TRABAJAR

Caracterización del autómata a pila

7-tupla 𝑀 = {, Γ , 𝑄, 𝐴0, 𝑞0 , 𝑓, 𝐹}  = {𝑎, 𝑏} Γ=𝜆 Q = {𝑞0 , 𝑞1 } A0 = 𝜆 𝑞0 = 𝑞0 F = 𝑞1 f = 𝑓𝑢𝑛𝑐𝑖ó𝑛 𝑑𝑒 𝑡𝑟𝑎𝑛𝑠𝑖𝑐𝑖ó𝑛 𝛿 = (𝑞0 , 𝑎, 𝜆; 𝑎), (𝑞0 , 𝑎) 𝛿 = (𝑞0 , 𝑏, 𝑎; 𝜆), (𝑞1 , 𝜆) 𝛿 = (𝑞1 , 𝑏, 𝑎; 𝜆), (𝑞1 , 𝜆) AP Pila vacía Estado No es necesario que Final tenga un estado de aceptación en el autómata Estado de La pila debe quedar la pila vacía para que el autómata finalice

AP Estado de Aceptación Es necesario representar un estado de aceptación en el autómata, el cual define el final del autómata. La pila puede no estar vacía.

Procedimiento paso a paso del recorrido de una cadena

1. Cuando el autómata se encuentra en el estado 𝑞0 lee el símbolo de entrada a y tiene el símbolo 𝜆 (vacío) en la cima de la pila.

2. El procedimiento se repetirá n veces en el estado 𝑞0 mientras el símbolo de entrada sea a aumentado la cantidad de a en la pila. 3. Cuando el autómata se encuentra en el estado 𝑞0 lee el símbolo de entrada b pasará a un estado 𝑞1 eliminando una a de la pila dejando este espacio 𝜆 (vacío)

4. El procedimiento se sigue repitiendo n veces mientras se reciba b como símbolo de entrada

Practicar y verificar lo aprendido

Por estado final, solo serán aceptadas aquellas cadenas que arranquen con aa

3.3.

Autómata de Pila [Ricardo Rodríguez]

El diseño solicitado corresponde al diligenciamiento de la siguiente tabla:

3.4.

Autómata de Pila [Jenny Monsalve]

El diseño solicitado corresponde al diligenciamiento de la siguiente tabla:

4. CONCLUSIONES Xxxxxxxxxxxxxxxxxx

Yyyyyyyyyyyyyyyyyyy

zzzzzzzzzzzzzzzzzzzzzzzzzzz

5. REFERENCIAS BIBLIOGRÁFICAS González, A. [Ángela] (2017, mayo 16). Minimización de un autómata. [Archivo de video]. Recuperado de: https://www.youtube.com/watch?time_continue=3&v=eOynYG8Ibk0

González, A. [Ángela]. (2018, junio 1). Lenguajes Independientes del Contexto. [Archivo web]. Recuperado de http://hdl.handle.net/10596/18317

Carrasco, R., Calera, R., Forcada, M. (2016). Teoría De Lenguajes, Gramáticas Y Autómatas Para Informáticos. (pp. 119 - 127). Recuperado de http://bibliotecavirtual.unad.edu.co:2051/login.aspx?direct=true&db=nlebk&AN=318032& lang=es&site=edslive&ebv=EB&ppid=pp_Cover