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.

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

Gramática hexadecimalabrimos el JFlap y pinchamos en la opción “Grammar”

nueva Gramática JFlap

modelamos la gramática

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

Input grammar JFlap

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

Árbol derivación 5b3

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

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:

Gramática libre de contexto pregunta 1

abrimos el JFlap y comprobamos si acepta las palabras del lenguaje

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

Verificar Gramatica

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.

Gramática libre de contexto pregunta 2

verificamos algunas palabras en el JFlap

JFlap Gramatica 2

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