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
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
aabbbb
Como generas las trazas del apartado C?
igual que para el resto de los autómatas en el menú input
y en q opción del jflap insertas el automata de pila?
Pushdown Automaton, después te pregunta si lo quieres simple o con entrada de múltiples caracteres
Hola, en el apartado c, Como generas el automata partir de gramática en forma normal de Chomsky
lee bien el apartado b, allí esta el proceso de conversión
No entendi bien lo del apartado C.
No tngo problema en generar las gramáticas pero no se como generar las trazas. Puede decir como generar el automata a partir de la gramatica? Ahora q se acaba el curso, muchas gracias por la ayuda.
Pep, para obtener las trazas para palabras que deseamos probar seleccionamos la opción “Step by State” en el menú “input”, escribes la palabra y los estados en verde son palabras aceptadas
pero para hacer las trazas con step by state hay que generar primero el automata, tanto partiendo de la gramatica de chomsky como de la libre de contexto.
Y no se como generar el automata.
Perdona por dar tanto el coñazo
Si quieres quedamos en la cafetería de la facultad y te lo explico
Tienes la respuesta a tus dudas en el Segundo examen modelo 2 espero que te sirva de ayuda
Disculpa, me podrias dar el nombre del programa que estas usando, para realizar ésto? gracias.
JFlap lo puedes descargar de aqui http://www.cs.duke.edu/csed/jflap/
hola tengo poco progrmando en java, me encargaron una terea de un automata de pila que convierta a AFND-transicion lambda , AFND,
AFD.
podrian pro porcinarme el codigo para empesar aimplementarlo.
No tengo ese codigo, ni tiempo para escribirlo.
Loo siento
Hola, podrías ayudarme a crear un automata de pila para modelar algunos lenguajes, por favor, gracias