MODELAR PROBLEMAS DE LENGUAJES INDEPENDIENTES DEL CONTEXTO Unidad 2 – Fase 3: Actividad Intermedia PRESENTADO POR: Jenn
Views 194 Downloads 0 File size 664KB
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