JFlap – La Fabulosa Vida de un IT

26/05/2010

Segundo Examen Practico TALF Modelo 3

Este esta incompleto si algun alma caritativa copio el primer ejercicio lo puede poner en los comentarios.

Ejercicio 2: Describe el lenguaje que genera la siguiente gramática.

Respuesta genera palindromos

Ejercicio 3: Crea una gramática que genere números hexadecimales e indicar el arbol de derivación para 5b3

La gramática que genera números hexadecimales es la siguiente:

abrimos el JFlap y pinchamos en la opción “Grammar”

modelamos la gramática

para generar el árbol de derivación utilizamos la opción “Brute Force Parse” en el menú “Input” que nos abrirá una nueva pestaña

introducimos 5b3 en la caja de texto y pinchamos en “Start” esperamos que acepte la palabra para luego presionar en el botón “step” hasta obtener el árbol de derivación completo que es el siguiente

26/05/2010

Segundo Examen Practico TALF Modelo 2

1. Comprobar si son equivalentes:

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

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”

insertamos la expresión regular en el JFlap λ

Ahora la convertimos en un autómata con la opción “Convert NFA” del menú “convert”

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

guardamos 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”

modelamos la gramática en la nueva ventana

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

pinchamos en “Show All” y “Export” lo que nos creara un autómata equivalente a la gramática

ahora con los tres autómatas abiertos vamos a comparar equivalencias

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

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

pinchamos en “Do All” y “Procceed” y se creara una nueva pestaña

Pinchamos en “Do All” y “Export” y aparecerá la gramática convertida a forma normal de 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

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

c) 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

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

15/05/2010

Hoja 11 (11 de Mayo de 2010)

P1: Construye una gramática libre de contexto G que genera todas las palabras sobre el alfabeto {a, b} que tienen el mismo número de a’s y b’s, es decir,

L(G) = {ε, ab, ba, aabb, abab, baab, abba, baba, bbaa, aaabbb, aababb, . . .}

La gramática a generada es la siguiente:

abrimos el JFlap y comprobamos si acepta las palabras del lenguaje

generamos un archivo con diversas palabras con los caracteres a y b para verificar que no acepta las palabras que no cumplen la regla

P2: Construye una gramática libre de contexto G que genera todas las palabras sobre el alfabeto {a, b} que tienen un número diferente de a’s y b’s (ayuda: amplía la gramática del primer punto).

Para construir esta gramatica nos basaremos en las producciones anteriores evitando la producción de la palabra vaciá y dividiendo el problema en dos grupos palabras con mayor numero de letras a que de b (A) y palabras con mayor numero de letras b que de a (B). para ello simplemente evitaremos que las producciones terminales de A y B generen ε y permitan introducir un numero ilimitado de as y de bes.

verificamos algunas palabras en el JFlap

27/04/2010

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

introducimos la expresión regular en el cuadro de dialogo

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

Convertimos el AFND en un AFD usando la opción “Convert to DFA” del menú Convert

como 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

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

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

Aparece una nueva Ventana con el FA generado

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

son equivalentes

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

para 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

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)*)*

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

una vez generada la gramática solo resta pulsar en el botón Export que abrirá una nueva ventana con la 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

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

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