1. Comprobar si son equivalentes:
a)
- S -> aaS
- S -> bB
- B -> bB
- B -> b
b)
![Autómata comprobar equivalencia examen Autómata comprobar equivalencia examen](https://www.luzem.com/wp-content/uploads/2010/05/Automata_comprobar_equivalencia_examen-300x166.png)
c)
![Expresión Regular Expresión Regular](https://www.luzem.com/wp-content/uploads/2010/05/regexp_html_60167a7e.gif)
para compara si los anteriores elementos debemos transformar la expresión regular y la gramática en una expresión regular
para la expresión regular los pasos son los siguientes :
Abrimos el JFlap y seleccionamos la Opción “Regular Expression”
![Expresion Regular JFlap Expresion Regular JFlap](https://www.luzem.com/wp-content/uploads/2010/05/Expresion_Regular.png)
insertamos la expresión regular en el JFlap λ
![Expresión regular insertada Expresión regular insertada](https://www.luzem.com/wp-content/uploads/2010/05/Expresion_regular.png)
Ahora la convertimos en un autómata con la opción “Convert NFA” del menú “convert”
![Convirtiendo expresión regular en autómata finito no determinista Convirtiendo expresión regular en autómata finito no determinista](https://www.luzem.com/wp-content/uploads/2010/05/Convirtiendo_Expresion_Regular_En_Automata_Finito_No_Determinista-300x241.png)
pinchamos en “Do All” y “Export” lo que nos mostrara una nueva ventana con el autómata equivalente a la expresión regular
guardamos el autómata generado para compararlo después .
Seguidamente modelamos la gramática en JFlap para ello abrimos el JFlap y seleccionamos la opción “Grammar”
modelamos la gramática en la nueva ventana
como es una gramática lineal por la derecha seleccionamos la opción “Convert Right Lineal Grammar to FA” en el menú “Convert”
pinchamos en “Show All” y “Export” lo que nos creara un autómata equivalente a la gramática
ahora con los tres autómatas abiertos vamos a comparar equivalencias
![Tres automatas abiertos Tres automatas abiertos](https://www.luzem.com/wp-content/uploads/2010/05/Tres_automatas_abiertos-300x152.png)
Para comparar la equivalencia entre autómatas seleccionamos la opción “Compare Equivalence” en el menú “Test” lo que nos preguntara con que autómata queremos comparar
El resultado es: La gramática y la expresión regular son equivalentes
2. Dada a seguinte gramática
- A -> CB2
- A -> 1B
- A -> ε
- B -> BC
- B ->1
- C -> 2
a) Transformar a forma normal de Chomsky
modelamos la gramática en JFLAP
Para convertirla a Chomsky seleccionamos la opción “Transform Grammar” en el menú “Convert“, nos advierte que eliminara el símbolo Lambda
pinchamos en “Do All” y “Procceed” y se creara una nueva pestaña
Pinchamos en “Do All” y “Export” y aparecerá la gramática convertida a forma normal de Chomsky
![Gramática convertida a Chomsky Gramática convertida a Chomsky](https://www.luzem.com/wp-content/uploads/2010/05/Gramatica_Convertida_a_Chomsky-300x232.png)
b) Convertir a resultante a un autómata de pila polo método LL
Sobre la gramática generada pinchamos en la opción “Convert CFG to PDA (LL)” en el menú “Convert” nos abrirá una nueva pestaña
![Convert to PDA LL Convert to PDA LL](https://www.luzem.com/wp-content/uploads/2010/05/Convert_to_PDA_LL-300x205.png)
pinchamos en “Show All” y “Export” lo que nos mostrara el autómata de pila
c) Obten a traza para a cadea de entrada 1122
Menú “Input” opción “Step by State” abre un dialogo insertamos la cadena 1122 y seleccionamos Final State
le damos a step hasta que aparezca un estado en verde lo seleccionamos y pinchamos en trace la traza final es la siguiente:
![Traza Completa Traza Completa](https://www.luzem.com/wp-content/uploads/2010/05/Traza_Completa-121x300.png)