AUTOMATAS Y LENGUAJES FORMALES
UNIDAD 2 - FASE 3 - MODELAR PROBLEMAS DE LENGUAJES
INDEPENDIENTES DEL CONTEXTO.
TUTOR:
VERMEN RAINER AYALA
JORGE LUIS ZARACHE
CÓD. 72433142
CURSO 301405A_761
GRUPO 301405_69
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA.
BARRANQUILLA
ABRIL, 2020.
EJERCICIOS DE LA FASE 2
ACTIVIDAD INDIVIDUAL
De acuerdo al último dígito de su cédula o tarjeta de identidad, identifique el ejercicio
asignado en la siguiente tabla:
Último dígito de la Ejercicio
Cédula o TI
1y9 Ejercicio 1
2y8 Ejercicio 2
3y7 Ejercicio 3
4y6 Ejercicio 4
5y0 Ejercicio 5
ACTIVIDAD 1: Autómatas de Pila
1. Ejercicio 1 2. Ejercicio 2
3. Ejercicio 3 4. Ejercicio 4
5. Ejercicio 5
El diseño solicitado corresponde al diligenciamiento de la siguiente tabla:
Ejercicio a Ejercicio 3
Trabajar
Caracterizació En este espacio se realiza:
n del Autómata Mediante la definición formal explicar las características del autómata:
Formalmente un autómata de pila se define mediante una séptupla, así:
a Pila
Autómata de Pila = (Σ, Γ, Q, A0, q0, f, F), donde:
1) Σ = Alfabeto de Entrada = {0,1}
2) Γ = Alfabeto de la Pila = {B,C,Z}
3) Q = Conjunto finito de estados = {q 0 ,q 1 }
4) A0 ∈ Γ = Símbolo inicial de la Pila = { λ }
5) q 0 ∈ Q = Estado inicial del Autómata = {q 0}
6) F ⊆ Q = Estados finales del Autómata = {q 0 ,q 1 }
7) f (δ ) = Función de transición =
Q Σ Γ Movimiento
q0 0 Z (q 0 , B)
q0 0 C (q 0 , BC )
q0 0 B (q 0 ,C)
q0 λ Z (q1 , λ )
q0 1 C (q1 , λ )
q1 1 C (q1 , λ )
Realizar un cuadro comparativo de la Equivalencia entre AP por vaciado de pila
y AP por estado final:
Hay 2 tipos de AP; donde ambos son equivalentes.
Cuadro Comparativo.
AP por Estado Final AP Vaciado de Pila
Sea P=(Q , Σ , Γ , δ , q 0 , Z 0 , F ),un Para todo AP P = (Q, Σ, Γ, δ, q 0,
AP Z 0), se define el lenguaje que
L ( P), el lenguaje aceptado por P acepta como:
por estado final es: N(P) = {w | ( q 0, w, Z0) ├* (q, ε, ε)}
{ w | ( q 0, w, Z0) ├* (q, ε, α)} para cualquier estado (q).
Para algún estado q de F y cual-
quier cadena de pila α Ejemplo:
modificar el AP de la figura para que
Ejemplo: reconozca también por vaciado de
El AP de la figura acepta cadenas pila, se cambia (δ) ( q1, ε, Z0) = {( q
x por estado final si y sólo si (x) tiene 2, Z0)} por δ ( q1, ε, Z0) = {( q 2, ε)}
la forma ww R
Procedimiento Realice de manera detallada y grafica el procedimiento paso a paso del
de paso a paso recorrido de una cadena (La cadena la selecciona el estudiante, debe
del recorrido contener como mínimo 8 caracteres) en el autómata a pila. Describir cómo
de una cadena funciona el almacenamiento en la pila, como funciona LIFO, etc.
- Paso 1…
- Paso 2…
- Paso 3…
Ejemplo:
Gráfico
Realizar la representación utilizando flechas, conexiones, diagramas
que permitan ver el funcionamiento del autómata a pila
Para una transición:
F (q, a, A) = {(q1, Z1), (q2, Z2),... (qn, Zn)}
- Paso 1: cuando el autómata se encuentra en el estado q, lee el símbolo de
entrada a y tiene el símbolo A en la cima de la pila.
- Paso 2: El autómata pasará a algún estado q1, eliminará el símbolo A de
la pila e introducirá en ella la palabra Zi, quedando la cabeza de Zi en la
cima de la pila.
- Paso 3: El procedimiento se repite n veces
Practicar y Apoyándose en el simulador JFlap o VAS ejecutar y validar por lo menos
verificar lo cinco cadenas válidas y 5 cadenas rechadas por el autómata. En este
aprendido espacio adjunta la imagen.
Lenguaje Agregar el lenguaje regular del automata
regular
Actividad 3:
Teniendo en cuenta el siguiente autómata realice:
1. Describa la forma matemática del autómata,
2. Plasme la tabla de transición.
3. Identifique los elementos (tupla, estado final, inicial, alfabeto, etc.). Debe explicar
y describir cada elemento y la función y significado en el autómata. Conceptos y
definiciones adicionales.
4. Muestre en el simulador (gráficamente) como recorre una cadena válida. Explique
cada secuencia. (No se trata solo de captura las imágenes, estas deben ser
explicadas en pié de página o de lo contrario no tienen validez)
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.
(Ventajas que ofrezca uno u otro).
Solución:
1. Describa la forma matemática del autómata.
Forma matemática de un AFND. δ :Qx { Σ ⋃ ϵ } ⟶ P ( Q )
2. Plasme la tabla de transición.
Estados a b
⩥ q0 q4 q 0 ,q 3
q1 q1 q4
q3 q4 q1
q4 q0 q4
3. Identifique los elementos (tupla, estado final, inicial, alfabeto, etc.). Debe explicar
y describir cada elemento y la función y significado en el autómata. Conceptos y
definiciones adicionales.
Propiedades:
AFND: Quíntupla de 5 elementos ( Q , Σ , S , F , δ ) .
Q : Conjunto de estados Finitos ={q0 , q1 , q3 , q4 }
Σ: Alfabeto de Entradas = {a,b}
SϵQ: Es el estado inicial = {q 0}
F ⊆Q : Es un conjunto de estados finales = {q1 , q4 }
δ :Qx {Σ ⋃ ϵ }⟶ P(Q) = Es la función de la transición, donde:
δ ( q0 , a ) ={q 4 }
δ ( q0 , b ) ={q 0 ,q 3 }
δ ( q1 , a )={q 1 }
δ ( q1 , b )={q 4 }
δ ( q3 , a ) ={q 4 }
δ ( q3 , b ) ={q 1 }
δ ( q4 , a )={q0 }
δ ( q4 , b )={q4 }
4. Muestre en el simulador (gráficamente) como recorre una cadena válida.
Explique cada secuencia. (No se trata solo de captura las imágenes, estas deben
ser explicadas en pié de página o de lo contrario no tienen validez)
Se introduce la cadena de caracteres {aabbb}, para comprobar su recorrido en el autómata,
así:
El autómata inicia su
proceso en el estado
inicial q 0
En el autómata se
hace el proceso del
carácter a, al
estadoq 4
Se hace el bucle,
entre el estado q 4 y
q 0, con carácter a
Inicia el proceso en
q 0, con el carácter
b
Inicia el recorrido
hacia q 3, con el
carácter b
Final mente inicia el
recorrido hacia q 1,
que es el estado de
aceptación, con el
carácter b
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.
(Ventajas que ofrezca uno u otro).
Las diferencias y similitudes entre los dos simuladores son:
Procesos de edición; JFLAP, no permite editar el nombre de sus estados, a diferencia de
VAS.
Procesos de edición; VAS, permite el cambio en el tamaño en momento de diseño, JFLAP,
es rígido en este tema.
Elección de tipo de autómata; JFLAP, permite elegir el tipo de autómata deseado, VAS,
solo se puede crear AF y Maquinas de Turing.
En los simuladores JFLAP, VAS es posible la construcción de un diagrama de Moore para
AFD y AFND.
En los simuladores JFLAP, VAS es posible realizar pruebas de cadenas de entrada.
Referencias Bibliográficas.
Millán, J. Antonio J. (2009). Compiladores y procesadores de lenguajes. (pp. 28-62).
Recuperado de [Link]
docID=10844351
Alemán. H. [Helena]. (2017, Junio 19). Conceptualización de autómata [Archivo de
video].Recuperado de [Link]
Alemán. H. [Helena]. (2018, mayo 23). Expresión Regular [Archivo de video]. Recuperado
de [Link]
González, A. [Ángela]. (2016, mayo 30).Conversión de Autómata Finito No Determinista a
Autómata Finito Determinista [Archivo de video]. Recuperado de
[Link]
González, A. [Ángela]. (2016, mayo 30).Conversión de Autómata Finito No Determinista a
Autómata Finito Determinista con transiciones vacías – Método 1. [Archivo de video].
Recuperado de [Link]
