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

Gramática introducida JFlapuna 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

Convirtiendo gramática libre de contexto a autómata finito de pilaPinchamos en el botón “Show all” para seleccionar todas las producciones y seguidamente en “export” con lo que obtendremos nuestro autómata de pila.

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 ε

Transform grammar lambda problemaceptamos 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

Eliminacion lambda JFlapPaso 2. Conversión a Chomsky

Chomsky converter JFlap

Al pinchar en el botón “export”  obtendremos nuestra gramática en forma normal de Chomsky.

Gramática 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 :

Traza xy AFP gramática

para el AFP generado a partir de la gramática en forma normal de Chomsky:

Traza XY gramática Forma Normal Chomsky

xxxyyyyyy

para el AFP generado a partir de la gramática libre de contexto :

Traza xxxyyyyyy AFP generada de gramática

para el AFP generado a partir de la gramática en forma normal de Chomsky:

Gran Traza 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 :

Traza epsilon 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”

Autómata de pila JFlap

seleccionamos la opción “Single Character Input” y modelamos el autómata en JFlap

Autómata de pila pregunta 2

para obtener las trazas para palabras que deseamos probar seleccionamos la opción “Step by State” en el menú “input

aabb

Traza aabbopci

aabbbb

Traza aabbbb

abtraza ababb

Traza abb

16 Replies to “Practica 9: Autómatas de pila con JFLAP”

  1. Hola, en el apartado c, Como generas el automata partir de gramática en forma normal de Chomsky

  2. 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.

    1. 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

  3. 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

  4. Disculpa, me podrias dar el nombre del programa que estas usando, para realizar ésto? gracias.

  5. 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.

  6. Hola, podrías ayudarme a crear un automata de pila para modelar algunos lenguajes, por favor, gracias

Leave a Reply to luzem Cancel reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.