Y navegando por Internet me encontré una practica de IG
http://rodland.blogsome.com/2005/06/29/practica-de-informatica-grafica/
Enjoy
Practica 9: Autómatas de pila con JFLAP
El enunciado en este enlace Practica 9:Autómatas de pila
1. Dada la siguiente gramática libre de contexto
- S → λ
- S → xAy
- A → λ
- A → xAy
- S → xByy
- B → xByy
- B → λ
a. Crea un autómata de pila que acepte el lenguaje generado por dicha gramática
Seleccionamos la opción grammar en JFlap e introducimos la gramática
una vez introducida la gramática seleccionamos el menú “Convert” y seleccionamos la opción “Convert CFG to PDA (LL)” nos mostrara una nueva pestaña para realizar la conversión
Pinchamos en el botón “Show all” para seleccionar todas las producciones y seguidamente en “export” con lo que obtendremos nuestro autómata de pila.
b. Transfórmala a forma normal de Chomsky.
Sobre la gramática anterior seleccionamos la opción “Transform Grammar” en el menú “Convert“
nos mostrara un mensaje de que la nueva gramática no generara la palabra ε
aceptamos el mensaje y aparecerá una nueva pestaña indicándonos las acciones a realizar para transformar la gramática.
paso 1 seleccionar símbolos que generen ε para eliminarlos
Paso 2. Conversión a Chomsky
Al pinchar en el botón “export” obtendremos nuestra gramática en forma normal de Chomsky.
c. Comprueba la equivalencia de los autómatas al menos con las siguientes palabras, e indica la traza en cada caso
para obtener las trazas para palabras que deseamos probar seleccionamos la opción “Step by State” en el menú “input“
xyyy
para el AFP generado a partir de la gramática libre de contexto :
Rechaza la palabra.
para el AFP generado a partir de la gramática en forma normal de Chomsky:
Rechaza la palabra.
xy
para el AFP generado a partir de la gramática libre de contexto :
para el AFP generado a partir de la gramática en forma normal de Chomsky:
xxxyyyyyy
para el AFP generado a partir de la gramática libre de contexto :
para el AFP generado a partir de la gramática en forma normal de Chomsky:
xyxy
para el AFP generado a partir de la gramática libre de contexto :
Rechaza la palabra
para el AFP generado a partir de la gramática en forma normal de Chomsky:
Rechaza la palabra
ε
para el AFP generado a partir de la gramática libre de contexto :
para el AFP generado a partir de la gramática en forma normal de Chomsky:
Rechaza la palabra
d. Intenta describir que lenguaje genera
el lenguaje esta formado por la palabra vacio, o por un conjunto de caracteres x seguidos de un conjunto de caracteres y.
2. Prueba cadenas reconocidas por el siguiente autómata de pila
para insertar el autómata de pila en JFlap seleccionamos “Pusdown Automaton”
seleccionamos la opción “Single Character Input” y modelamos el autómata en JFlap
para obtener las trazas para palabras que deseamos probar seleccionamos la opción “Step by State” en el menú “input”
aabb
opciaabbbb
ab
abb
