Segundo Examen Practico TALF Modelo 1

Modelo 1

Dada a expresión regular (a+b)*cc(b+a)*
Debuxa o autómata mínimo determinista completo equivalente

Abrimos el JFlap y seleccionamos la opción “Regular Expression”

Regular Expression JFlap

nos aparece una ventana para introducir la expresión regular, la introducimos

expresión regular Introducida

primeramente tendremos que transformarla en un autómata seleccionamos la opción “Convert to NFA” en el menú “Convert” nos abrirá una ventana para iniciar la conversión.

Regexp to NFA JFlapPinchamos en el botón “Do All”  y en “Export”  con lo que obtendremos un autómata que acepta las mismas palabras que la expresión regular.

Expresión regular transformada en un autómata

este autómata no es mínimo por lo tanto debemos minimizarlo para eso debemos transformarlo en un autómata determinista, para ello seleccionamos la opción “convert to DFA” en el menú “Convert

Convirtiendo de No determinista en determinista

Pinchamos en el botón “Complete” y luego en “Done” con lo que aparecerá una nueva ventana con el autómata determinista

Autómata determinista convertidoEste autómata determinista puede no ser mínimo así que lo necesitamos minimizar, para ello seleccionamos la opción “Minimize DFA” en el menú “Convert”  lo que nos abrirá una nueva pestaña para realizar la conversión

DFA Minimizacion JFlapSeleccionamos el nodo raíz del árbol “El que no tiene ningún nodo superior” y pinchamos en “Complete Subtree” para luego pinchar en “Finish” con lo que creara una nueva ventana para la minimización

minimizacion AFDpinchamos en “Complete” y en “Done” lo que nos creara una nueva ventana con el autómata mínimo

Autómata mínimo

pero este autómata no es completo para eso introduciremos un estado de error al que dirigiremos todas las transiciones que no pertenezcan al autómata.

Autómata mínimo completo

Indica si dita expresión regular e equivalente a seguinte gramática, e o proceso seguido para averigualo.

  • S-    ->    B
  • A    ->    ε
  • B    ->    C
  • C    ->    B
  • I    ->    A
  • C    ->    D
  • E    ->    F
  • I    ->    H
  • H    ->    J
  • K    ->    I
  • J    ->    L
  • O    ->    K
  • M    ->    K
  • Q    ->    C
  • D    ->    cE
  • H    ->    I
  • P    ->    R
  • R    ->    aT
  • N    ->    aO
  • P    ->    U
  • L    ->    bM
  • J    ->    N
  • V    ->    Q
  • F    ->    cG
  • B    ->    P
  • G    ->    H
  • T    ->    Q
  • U    ->    bV

Abrimos el JFlap y creamos una gramática nueva

Creando gramática JFlapinsertamos la gramática

Gramática Insertadauna vez insertada la gramática necesitamos convertirla en un autómata para  verificar si es equivalente al autómata mínimo del apartado anterior para ello seleccionamos la opción “Convert Right-Lineal Grammar to FA” en el menú “Convert” nos abrirá la siguiente ventana.

Convirtiendo Grammar to FApinchamos en “Show All” para seleccionar todas las producciones, y en “Export” lo que nos creara una ventana con un Autómata equivalente a la gramática

Autómata equivalenteAhora es el momento de comprobar la equivalencia entre autómatas para ello abrimos el autómata mínimo completo del apartado anterior y en la ventana de cualquiera de los dos autómatas seleccionamos la opción  “Compare Equivalence” en el menú test nos abrirá una ventana preguntado que autómata queremos comparar y nos mostrara que SON EQUIVALENTES

Equivalentes

2 Dada a gramatica
S-> S mais S | S cuadrado | S cubo | raiz S | X
X-> XX | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Indica si acepta as seguintes expresións, e en caso afirmativo, obter o árbore de derivación proporcionado polo JFlap

Abrimos JFlap y seleccionamos la opción Grammar

Creando gramática JFlappara modelar la gramática deberemos cambiaremos las palabras mais por a, cuadrado por b, cubo por c y raiz por d. Modelamos la gramatica

Gramática ejercicio 2para obtener el árbol de derivación seleccionamos la opción “Brute Force Parse” en el menú “input” lo que nos abrirá la siguiente ventana

Brute force parse grammar JFlapintroducimos la palabra a probar  en la caja de texto input y pinchamos en  “Start”

luego pincharemos en step hasta que nos complete el árbol de derivación

  • 00 mais 15 cubo (00a15c)

árbol 00a15c

  • raiz 123 cuadrado (d123b)

arbol d123b

  • 7 mas raiz 3 (7ad3)

arbol 7ad3

3 Replies to “Segundo Examen Practico TALF Modelo 1”

Leave a Reply

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