Practica 7 Conversiones Autómatas lenguajes regexp en JFlap

El enunciado de la practica aqui:Practica 7 TALF

1.-Encuentra el AFD mínimo que reconoce el lenguaje representado por la expresión regular (RegEx) siguiente (00+10*1+λ)*(1+00)

En JFlap escogemos la opción de expresión regular

1 1 expresion regularintroducimos la expresión regular en el cuadro de dialogo

1 2 expresion regular

seleccionamos la opción Convert to NFA del menu convert para convertir una expresión regular en un autómata finito no determinista lo que nos creara el siguiente AFND

1 3 autómata finito no deterministaConvertimos el AFND en un AFD usando  la opción “Convert to DFA” del menú Convert

1 4 automata finito deterministacomo ultimo paso debemos minimizar el autómata finito determinista la opción para realizar la minimización se encuentre en el menú Convert  en la opción minimize DFA

1 5 automata finito determinista minimo

2.-Encuentra el AFD mínimo que reconoce el lenguaje representado por la siguiente gramática, y comprueba si es equivalente al del ejercicio anterior

S → 0A
S → 1C
D → 1C
B → 0B
C → 1S
D → 0A
A → 0D
C → 0B
B → 1S
S →1
D→1
A→0

Introducimos la gramática en JFlap

1 Gramatica Introducida

Pinchamos en Convert –> Convert Right Lineal Grammar to FA nos aparece una ventana donde introducimos la siguiente secuencia Show all -> Done? –> Export

2 Conversion a FA

Aparece una nueva Ventana con el FA generado
3 FA Convertido

Seleccionamos el menu test -> compare equivalence –> seleccionamos el AFD minimo del apartado anterior

4 equivalencia

son equivalentes

3.-Encuentra una expresión regular y una gramática para el lenguaje reconocido por el autómata siguiente

1 automatapara convertir el autómata en una expresión regular seleccionamos la opción “convert FA to RE” del menú “convert” que nos obligara a añadir un estado final que no sea inicial quedando de la siguiente forma

autómata a expresión regular

pinchamos en el botón “Do It” hasta que realice todos los pasos necesarios para la conversión informándonos en este punto con un mensaje con el siguiente text “You’re done. Go away.”  momento en el que pincharemos en export que nos mostrara la expresión regular en una nueva ventana.

(b(ab)*+(a+b(ab)*(b+aa))(ba+(a+bb)(ab)*(b+aa))*(a+bb)(ab)*)*

(b(ab)*+(a+b(ab)*(b+aa))(ba+(a+bb)(ab)*(b+aa))*(a+bb)(ab)*)*

para convertir el autómata en una gramática en la ventana del autómata seleccionamos “Convert to Grammar” en el menú “Convert”   y presionamos repetidamente el botón “Hint” repetidas veces hasta que genere la gramática

conversión a gramática

una vez generada la gramática solo resta pulsar en el botón Export que abrirá una nueva ventana con la gramática

gramática

4.-Comprueba que el autómata anterior es equivalente a la siguiente Expresión Regular ((aa+b)(ba)*(a+bb+λ)+ab)*(aa+b)(ba)*+λ

JFlap no puede compara equivalencia entre expresiones regulares por lo tanto debemos transformar la expresión regular en un autómata para eso creamos una nueva expresión regular en JFlap

expresión regular

una vez insertada la expresión regular  seleccionamos la opción “Convert to NFA”  del menú “Convert”

regexp to AFN

Una vez generado el AFND solo necesitamos comprobar la equivalencia en el menú “Test” -> “Compare Equivalence” que nos dirá que son equivalentes, en este caso son equivalentes

AFN

Leave a 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.