Simplificacion de Gramaticas

TEORÍA DE AUTÓMATAS Y LENGUAJES
FORMALES
Práctica 5 - Simplificación de gramáticas
incontextuales
1. Objetivos
2. Representación de los datos en Mathematica
3. Eliminación de símbolos inútiles
3.1. Símbolos generativos
3.2. Símbolos alcanzables
3.3. Símbolos inútiles
4. Eliminación de producciones vacías
5. Eliminación de producciones unitarias
6. Simplificación general de gramáticas1. Objetivos.
La presente práctica presenta unos algoritmos que permiten obtener gramáticas
incontextuales (casi) equivalentes a una dada con determinadas propiedades
estructurales. La simplificación de gramáticas incontextuales afecta a tres aspectos
distintos pero interrelacionados :
Los símbolos inútiles de la gramática, que no inciden en la capacidad generativa a
la misma y que, porlo tanto, pueden ser eliminados sin variar el lenguaje de la
gramática.
Las producciones vacías, A -> λ, que como veremos, al ser eliminadas, provocan
una transformación en el resto de producciones cuyo efecto es una gramática que
define el mismo lenguaje menos λ.
Las producciones unitarias, A→B que, al igual que en el caso anterior, su
eliminación produce una transformación en la gramática,obteniendo, en este caso,
una gramática equivalente.
Los puntos que seguiremos para abordar las transformaciones anteriores son los
siguientes :

Formulación de los algoritmos de transformación en cada caso.
Integración de los algoritmos anteriores para finalmente obtener gramáticas
simplificadas

2. Representación de los datos en Mathematica
En una gramática incontextual G=(N,T,P,S)adoptaremos el siguiente convenio, las letras
mayúsculas denotaran símbolos auxiliares, el resto de símbolos, excepto → y |, denotarán
símbolos terminales. De este modo, para especificar la gramática basta dar el conjunto de
producciones de la misma.
Una cadena la representaremos por la lista asociada a sus símbolos (ej. abcd se representa
por {a,b,c,d} y, en el caso de que sea la cadena vacíaλ, se representará por {}). El
conjunto de A-producciones se representará por una lista con dos elementos, el primero
de ellos será el propio símbolo A y el segundo será a su vez una lista que contendrá como
elementos las listas asociadas a los consecuentes de las producciones. Veamos el
siguiente ejemplo
A → ABa | λ | abB

se representa por la lista

{A,{{A,B,a},{},{a,b,B}}}
Así , elconjunto de producciones P se representa por la lista de todas las Aproducciones. De esta forma, para la gramática
S → ab | λ | Ab
A → bba | S

se representará como

{{S,{{a,b},{},{A,b}}},{A,{{b,b,a},{S}}}}
Finalmente la gramática completamente especificada, se establece como una lista con
cuatro elementos { N, T, P, S }. Así, en el ejemplo anterior, la gramática completamente
especificadasería la lista
{ {S,A}, {a,b}, {{S,{{a,b},{},{A,b}}},{A,{{b,b,a},{S}}}}, S }

3. Eliminación de símbolos inútiles.
3.1. Símbolos generativos.
Los símbolos generativos asociados a una gramática incontextual son aquellos capaces de
generar en uno o más pasos de derivación cadenas formadas sólo por símbolos
terminales. El objetivo de este primer apartado consiste en detectar los símbolosgenerativos de una gramática incontextual y eliminar de la misma aquellos símbolos que
no los sean. El siguiente algoritmo nos proporciona el esquema de cálculo de los

símbolos auxiliares generativos de una gramática incontextual.
Algoritmo 1: Cálculo de los símbolos generativos de
una gramática
Entrada: G=(N,T,P,S)
Salida: gen, una lista de los símbolos generativos de la
gramática
Método:gen={}
gen2=T
Repetir
gen = { A ∈ N : A → x ∈ P, x ∈ gen2*}
gen = gen - gen2
gen2 = gen ∪ gen2
hasta gen = {}
gen=gen2 - T
fin_del_Método

Actividad 1
Dada una gramática incontextual {N,T,P,S} desarrollar un módulo Mathematica que
detecte los símbolos auxiliares que contienen producciones formadas únicamente por
símbolos terminales.
Actividad 2
Dada una gramática incontextual...