Segundo Examen Practico TALF Modelo 2

1. Comprobar si son equivalentes:

a)

  • S -> aaS
  • S -> bB
  • B -> bB
  • B -> b

b)

Autómata comprobar equivalencia examen

c)

Expresión Regular

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

insertamos la expresión regular en el JFlap λ

Expresión regular insertada

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

pinchamos en “Do All” y “Export”  lo que nos mostrara una nueva ventana con el autómata equivalente  a la expresión regular

Autómata Equivalente expresión regularguardamos 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

nueva Gramática JFlapmodelamos la gramática en la nueva ventana

Gramática modeladacomo es una gramática lineal por la derecha seleccionamos la opción “Convert Right Lineal Grammar to FA” en el menú “Convert

Convertir Gramática Lineal por la derecha a autómata finitopinchamos en “Show All” y  “Export” lo que nos creara un autómata equivalente a la gramática

Autómata Equivalente Gramáticaahora con los tres autómatas abiertos  vamos a comparar equivalencias

Tres automatas abiertos

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

Gramática a normalizarPara convertirla a Chomsky seleccionamos la opción “Transform Grammar” en el menú “Convert“, nos advierte que eliminara el símbolo Lambda

Eliminación símbolo vacíopinchamos en “Do All” y “Procceed” y se creara  una nueva pestaña

Conversión Chomsky JFlapPinchamos en “Do All” y “Export” y aparecerá la gramática convertida a forma normal de Chomsky

Gramática convertida a Chomsky

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

pinchamos en “Show All” y “Export” lo que nos mostrara el autómata de pila

Autómata de pilac) 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

Trazale damos a step hasta que aparezca un estado en verde lo seleccionamos y pinchamos en trace la traza final es la siguiente:

Traza Completa

2 Replies to “Segundo Examen Practico TALF Modelo 2”

  1. Pues por más que lo comparo, en el primer ejercicio, son equivalentes los 3 autómatas entre si, no solo la gramática y la EERR

Leave a Reply

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