Unidad 2 - Tarea 3 - Construcción de Autómatas de Pila
Presentado Por:
Eddie Enrique Leudo - Código: 1.077.460.105
Presentado a:
Tutor:
Edgar Antonio Cortes
Grupo Colaborativo: 301405_94
Universidad Nacional Abierta Y A Distancia – Unad
Escuela De Ciencias Básicas, Tecnología E Ingeniería
Autómatas y lenguajes formales
Octubre 2020
1
EJERCICIOS A DESARROLLAR
A continuación, se definen los ejercicios a desarrollar:
Ejercicios 1: Autómata de Pila
a. b.
c. d.
e.
Con el ejercicio seleccionado debe diligenciar la siguiente tabla:
EJERCICIO A Registre aquí el Ejercicio a trabajar. Por favor agregue la
TRABAJAR imagen
Caracterización del En este espacio se realiza:
autómata a pila - Mediante la definición formal explicar las características del
autómata, identificación de la séptupla.
R/
2
∑ : Es elelemento de entrada. ∑ ¿ {a ,b }
r : Es el alfabeto de pila . r={ λ , a }
Q : Es el conjunto de estados . Q={q0 , q1 }
AO E r : Es un simbolo especialde la pila . AO =λ
q 0 E Q : Es el estadoinicial del automata . q0 ℇ Q=q 0
F cQ : Es el conjunto de estados finales. F cQ=q1
f : Es una aplicacion denominada funcion de
transicion de ternas . F : δ =( q0 , a , λ ) ,(q 0 , a)
- Realizar la tabla de transición
R/
δ =( q0 , a , λ ) ,(q 0 , a)
δ =( q0 , b , a ) ,(q 1 , λ)
δ=( q1 ,b , a ) ,(q 1 , λ)
- Realizar un cuadro comparativo de la Equivalencia entre AP
por vaciado de pila y AP por estado final
AP por vaciado de pila AP por estado final
Este autómata realiza su Este estado se encarga de ir
recorrido de la cadena recorriendo la estructura del
leyendo cada carácter de este, autómata siguiendo los
apilando o desapilando caminos de este hasta llegar
símbolos según sea la al estado de aceptación o
instrucción del autómata. estado final de tal modo que
mientras el AP por vaciado
de pilas rechaza la cadena,
por estado final la acepta.
3
Procedimiento de Realice de manera detallada y grafica el procedimiento paso a
paso a paso del paso del recorrido de una cadena (La cadena la selecciona el
recorrido de una estudiante, debe contener como mínimo 5 caracteres) en el
cadena autómata a pila. Describir cómo 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 q0,
lee el símbolo a como aparece en el circulo verde, no
desapila por estar el símbolo λ, apila el símbolo A como
señala la flecha roja.
4
- Paso 2: El autómata continúa recorrido en el estado q0 lee
el símbolo siguiente de la cadena señalado con la flecha azul,
o sea la letra A, no desapila λ y apila la nueva A como lo
muestra la flecha roja.
- Paso 3: El autómata ahora vuelve a apilar símbolo A de la
cadena como lo muestra la flecha roja de la imagen porque leyó
el tercer símbolo de la cadena.
5
- Paso 4: Ahora el autómata recorre la cadena y lee la letra B,
desapila el símbolo A como lo muestra la flecha verde.
- Paso 5: Por último, el autómata el autómata al llegar a su estado
final lee el símbolo B que señala la flecha azul y desapila la
letra A y el resultado de la pila es el reflejado con el
semicírculo rojo.
6
7
Practicar y Apoyándose en el simulador JFlap (Anexo 1 - JFLAP) o VAS
verificar lo (Anexo 2- VAS) ejecutar y validar por lo menos cinco cadenas
aprendido válidas y 5 cadenas rechazadas por el autómata. En este espacio
adjunta la imagen.
Lenguaje Agregar el lenguaje regular del autómata
regular Lenguaje regular=¿
8
Ejercicios 2: Gramática del autómata
El estudiante realiza paso a paso la gramática del autómata que seleccionó.
Identifique su gramática (de forma manual) por la derecha o izquierda y la caracteriza.
Debe incluir el diagrama de estados con los componentes de la gramática asociados a las
variables y a las constantes.
R/
Estados Gramática
q0 aq 0 λ q0 aq 0
q0 bq 1 aq 1 λ q1
q1 bq 1 aq 1 λ q1
Ejercicio Grupal: Minimización de autómatas
Deben diligenciar la siguiente información:
9
10
EJERCICIO A Registre aquí el Ejercicio a trabajar. Por favor agregue la
TRABAJAR imagen
Procedimiento de Realice de manera detallada el procedimiento paso a paso de la
minimización minimización del autómata.
- Paso 1: Identificamos las transiciones del autómata
δ ( q0 , 1 )=q2
δ ( q0 , 2 )=q1
δ ( q1 ,1 )=q 0
δ ( q1 , 2 )=q 2
δ ( q2 , 1 )=q 3
δ ( q2 , 2 )=q 5
δ ( q3 , 1 )=q 1
δ ( q3 , 2 )=q 4
δ ( q 4 ,1 ) =q6
δ ( q 4 ,2 ) =q2
δ ( q5 , 1 )=q 7
δ ( q5 , 2 )=q 6
δ ( q6 , 1 )=q9
δ ( q6 , 2 )=q4
δ ( q7 , 1 )=q8
δ ( q7 , 2 )=q8
δ ( q8 , 1 )=q6
δ ( q8 , 2 )=q9
11
δ ( q9 , 1 )=q7
δ ( q9 , 2 )=q5
- Paso 2: Determinamos los conjuntos:
x={q3 , q5 , q7 } Aceptadores
y={q 0 , q 1 , q 2 , q 4 , q6 , q8 , q 9 } No Aceptadores
- Paso 3: Validamos la información de cada uno del conjunto x
1 2
q3 y y
q5 x y
q7 y y
q 3 , q 7=¿ Son equivalentes
conjunto y
1 2
q0 y y
q1 y y
q2 x x
q4 y y
q6 y y
q8 y y
q9 x x
q 0 ,q 1 ,q 4 , q6 , q 8=¿ Son equivalentes
q 2 , q 9=¿ Son equivalentes
- Paso 4: Generamos nuevos conjuntos
E={q 3 , q 7 } L={q5 } A={q 0 ,q 1 ,q 4 , q6 , q 8 } O={q2 , q 9 }
Validamos conjunto E
1 2
q3 A A
12
q7 A A
q 3 , q 7=¿ Son equivalentes
Validamos conjunto L
1 2
q5 E A
Validamos conjunto A
1 2
q0 O A
q1 A O
q4 A O
q6 O A
q8 A O
q 0 ,q 4 =¿ Son equivalentes
q 0 ,q 4 =¿ Son equivalentes
Validamos conjunto O
1 2
q2 E L
q9 E L
q 2 , q 9=¿ Son equivalentes
- Paso 5: Generamos nuevos conjuntos
E={q 3 , q 7 } L={q5 } A={q 0 ,q 6 } D={q1 , q 4 , q8 }
O={q2 , q 9 }
Validamos conjunto E
1 2
q3 A A
q7 A A
Validamos conjunto L
13
1 2
q5 E A
Validamos conjunto A
1 2
q0 O A
q6 O A
Validamos conjunto D
1 2
q1 A O
q4 A O
q8 A O
Validamos conjunto O
1 2
q2 E L
q9 E L
- Paso 6: Creando nueva tabla de transición
1 2
E A A
L E A
A O A
D A O
O E L
Resultado del Agregue aquí la imagen del autómata minimizado
Autómata
minimizado
14
Notación En este espacio agrega la notación formal del autómata.
formal del Identifique la quíntupla del autómata minimizado.
autómata Realice la tabla de transición
minimizado 5 tupla=(K ,∑ , δ , s , F)
M =( { A , D , E , O , L } , { 1,2 } , δ , A , {E , L })
K= A , D , E , O, L=¿ Estados
∑=1,2=¿ Alfabeto
s= A=¿ Estado inicial
F=E , L=¿ Estados finales
Tabla de transición
δ 1 2
A O A
D A O
# E A A
O E L
# L E O
15
Caracterización del Identifique los elementos (tupla, estado final, inicial, alfabeto,
autómata parte etc.). Debe explicar y describir cada elemento y la función y
teórica significado en el autómata. Conceptos y definiciones
adicionales.
R/
K= Esun conjunto finito de estados
∑= Es un alfabeto finito de simbolos de entrada
s= Es el estadoinicial en K
F=Es el conjunto de estados finales y de aceptacion
δ=Es la relacion de tranciones entre simbolo y estados
Lenguaje En este espacio agrega el lenguaje regular del autómata.
Regular
R/
Lenguaje regular :¿
Gramática del En este espacio agrega la gramática del autómata. Identifique su
autómata 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.
R/
Estados Gramática
A A1 A2
D D1 D2
E E1 E2
O O1 O2
L L1 L2
Validación de - Identifique 5 cadenas aceptadas y cinco cadenas rechazadas
cadenas
16
Practicar y Muestre en el simulador JFLAP (Anexo 1 - JFLAP) o VAS
verificar lo (Anexo 2- VAS) (gráficamente) como recorre una cadena válida.
aprendido Explique cada secuencia. (No se trata
solo de captura las imágenes, estas deben ser
17
explicadas en pie de página o de lo contrario no tienen validez)
R/
En la cadena aceptada 22212 el autómata recorre desde
el estado A formando la estrella de Kleene, pasa por
estado O y llega al estado de aceptación E.
En la cadena 222121 el autómata en el estado A forma
la estrella de Kleene recorre el estado O y luego el L,
llegando finalmente al E.
2212 arranca en estado A, luego pasa por O y
finalmente llega a L que también es un estado de
aceptación.
22121 arranca en A, recorre estado O, pasa por L y
llega a E.
2211 arranca en A pasa por O y llega por el atajo al
estado E.
22222221 Es una cadena de no alcanza a llegar a
ninguno de los estados de aceptación y lo mismo ocurre
con las demás cadenas que el nuevo autómata no
acepta.
18
Referencias
González, A. [Ángela]. (2018, junio 1). Lenguajes Independientes del Contexto. [Archivo web]. Recuperado de
http://hdl.handle.net/10596/18317
Piñeiro. M.A (2019) Gramáticas de autómatas. Hallar gramática parte 3. Recuperado de:
https://www.youtube.com/watch?v=KbqzW3bPrDo
19
