Practica 8 Gramáticas libres de contexto en JFLAP

El enunciado aquí 8 Gramaticas libres de contexto

1.- Sigue con el JFLAP el proceso de conversión a Forma Normal de Chomsky de la siguiente gramática

  • S → sA
  • A → BC
  • B →ε
  • A →a
  • C →ε

Abrimos JFlap y pinchamos en el botón “Grammar” nos aparecerá una ventana para introducir la gramatica

introduciendo gramática JFLAP

Introducimos las producciones para la gramática

gramática introducida en JFLAP

Para convertir la gramática a la forma normal de Chomsky seleccionamos la opción Convert -> Transform Grammar

Conversion JFLAP a forma normal ChomskyEsta conversión esta compuesta de varios pasos:

Eliminación de Landa

Conversión JFLAP Chomsky paso 1 eliminación epsilon

Eliminación de unitarias A->B

Eliminación de produciones unitarias

Eliminación de producciones no usadas

Eliminación de producciones no usadasY finalmente tras ajustar las producciones la conversión a Chomsky

Transformación producciones ChomskyLo cual nos generara la gramatica de Chomsky

Gramática Convertida

2. La gramática S → x | y | z | S + S | S – S | S * S | S/S | (S) es libre de contexto y sirve para expresiones enteras algebraicas sintácticamente correctas sobre las variables x, y, z. Comprueba si son correctas las siguientes expresiones, y obtén su árbol de derivación.

modelamos la gramática en JFlap

Gramatica Ejercicio 2Para comprobar las expresiones y obtener su árbol de derivación seleccionamos la opción Input->Brute Force Parse y en la caja de texto input introducimos la expresión a comprobar.
( x + y) –x

acepta la expresión con el siguiente arbol

(x+y)-z
( x + y ) * x – z

Acepta la expresión con el siguiente árbol

(x+y)*x-z

(( x + y ) / z)

Acepta la expresión con el siguiente árbol.

((x+y)/z)

((x+y)(x+z))

Rechaza la expresión

( x + y ) * x – z * y / ( x + x )

Al verificar la expresión utilizando brute force parse se satura es espacio del Heap por lo que no se puede verificar, si transformamos la gramática en una gramática lineal por la derecha y en un autómata finito podemos verificar si la expresión es valida en el automata.

Rechaza la expresión.

3. Describir el lenguaje generado por las siguientes reglas de producción
S → SS | aSb | bSa | ab | ba

ffff

4. Modelar e introducir en JFLAP la siguiente gramática básica de un idioma.

a. <frase> → <sujeto> <predicado>
b. <sujeto> → <articulo> <sustantivo>
c. <articulo> → el | la
d. <sustantivo> → mundo | río | niña
e. <predicado> → <verbo>
f. <verbo> → fluye | gira | llora

Forma todas las frases correctas

el mundo fluye
el mundo gira
el mundo llora
el río fluye
el río gira
el río llora
la niña fluye
la niña gira
la niña llora

Intenta crear una gramática más compleja, para expresar frases como.
El lado oculto de la luna permanece inexplorado
Las prácticas de TALF son entretenidas…