Unidad 5 Formas normales de Chomsky.

Una gramática formal está en Forma normal de Chomsky si todas sus reglas de producción son de alguna de las siguientes formas:

A → BC o
A → a o

donde A, B y C son símbolos no terminales (o variables) y α es un símbolo terminal.

Todo lenguaje independiente del contexto que no posee a la cadena vacía, es expresable por medio de una gramática en forma normal de Chomsky (GFNCH) y recíprocamente. Además, dada una gramática independiente del contexto, es posible algorítmicamente producir una GFNCH equivalente, es decir, que genera el mismo lenguaje.

Sea G = (∑ N, ∑T, P, $) una gramática con P ⊂ ∑N X (∑N U ∑T)* y X Є ∑N un símbolo no-terminal (o una variable). Podemos clasificar tales símbolos X en tres clases:

Variables accesibles:

• Si existe una derivación desde el símbolo inicial que contiene X, es decir, existe $ → * α Xβ donde α, β Є∑*

Variables generativas:

• Si existe una derivación desde el la variable que produce una sentencia , es decir, existe X →* ω donde ω Є *T.

Variables útiles:

• Si existe una derivación desde el símbolo inicial usando que produce una sentencia ω, es decir, existe $ →* α X β →*ω donde α, β Є ∑* y ω Є ∑*T.

Pasos para la la transformación de una gramática a la FNC

1º Eliminamos reglas unitarias.

A -> Ac
A -> w

Primero verificamos si en la gramática no hay reglas unitarias que obstruyan el desarrollo de FNC. Un ejemplo de una regla unitaria seria:

A -> X
X -> z

Como se puede observar, un No Terminal A deriva en otro No Terminal X, que a su vez deriva en un Terminal z, esto es redundante y por lo tanto se procede a eliminar el No Terminal X y pasando el Terminal z al No Terminal A

2º Eliminamos reglas no productivas

Una regla no productiva consiste en un No Terminal que nunca es accesible desde el No Terminal principal y sus respectivas derivaciones, del mismo o de las que provoquen sus No Terminal que se encuentren en su propia derivación. Un ejemplo de una regla no productiva seria:

A -> AZ
W -> X
Z -> c

En el ejemplo anterior el No Terminal W es una regla no productiva porque no es accesible desde el No Terminal principal que es A, ni de su derivación correspondiente que es AZ.
Nota: Este paso es omitido en el programa, por lo que no se verifica si un No Terminal es improductivo, por lo tanto, el usuario debe asegurarse de no introducir éste tipos de reglas.

3º Se procede a dar el formato correspondiente de la FNC.

La FNC (Forma Normal de Chomsky) sigue dos reglas básicas y únicas para tener el formato debido, estás son:

1) Un No Terminal solo puede derivarse en otros dos No Terminales.

2) Un No Terminal solo puede derivar en un Terminal.

Para la explicación de estas dos propiedades procedemos con un ejemplo:

Tenemos la siguiente gramática:

A -> cB+
B -> q

Nota: La gramática anterior no tiene ni reglas unitarias ni reglas no productivas, con lo que procedemos con el paso 3º.

Observemos la primera producción:

A -> cB+

1) Este No Terminal A deriva en cB+ donde como primer elemento de esta es un elemento Terminal, entonces procedemos a crear un No Terminal nuevo con este elemento y se lo agregamos al no Terminal A, respetando el orden de la gramática.

A -> ZB+
Z -> c

2) Una de las propiedades para la FNC es que un No Terminal solo puede derivar en otros dos No terminales, en nuestro ejemplo, tenemos el No Terminal A que deriva en ZB+, este contiene otro elemento terminal más, creamos un nuevo No Terminal para respetar la propiedad anteriormente descrita.

A -> ZY
Z -> c
Y -> B+

3) Podemos ver que los No Terminal A y Z cumplen con las propiedades de la FNC, excepto el No Terminal Y que deriva en un No Terminal y un Terminal, por lo que procedemos a crear el último No Terminal que cumpla la FNC.

A -> ZY
Z -> c
Y -> BX
X -> +

Por lo que se obtiene como resultado:

A -> ZY
Z -> c
Y -> BX
X -> +
B -> q


FORMA NORMAL DE GREIBACH

Una gramática independiente del contexto (GIC) está en Forma normal de Greibach (FNG) si todas y cada una de sus reglas de producción tienen un consecuente que empieza por un carácter del alfabeto, también llamado símbolo terminal. Formalmente, cualquiera de las reglas tendrá la estructura:
A − > aw

Donde "A" es el antecedente de la regla, que en el caso de las GIC debe ser necesariamente un solo símbolo auxiliar. Por su parte, "a" es el mencionado comienzo del consecuente y, por tanto, un símbolo terminal. Finalmente, "w" representa una concatenación genérica de elementos gramaticales, esto es, una sucesisión exclusivamente de auxiliares, inclusive, pudiera ser la palabra vacía; en este caso particular, se tendría una regla llamada "terminal":
A − > a

Existe un teorema que prueba que cualquier GIC, cuyo lenguaje no contiene a la palabra vacía, si no lo está ya, se puede transformar en otra equivalente que sí esté en FNG. Para su demostración, normalmente, se procede por contrucción, es decir, se plantea directamente un algoritmo capaz de obtener la FNG a partir de una GIC dada.

A partir de una GLC los pasos para transformarla a la FNG son lo siguientes: 

Paso1.Ordenar los alfabéticamente los elementos no terminales del lado izquierdo de las producciones.

Por ejemplo: A<B<C<…<S<…<Z

Paso2.Revisar los problemas de precedencia, los símbolos no terminales de mayor precedencia no pueden producir a elementos menores en la primera posición de las producciones.

Paso 3. Eliminación de recursión a la izquierda:

Si A →Aα1|Aα2|…|Aαr| β1|β2|…|βs

Donde el símbolo no terminal A contiene producciones con recursión a la izquierda y producciones sin recursión. Para solucionar este problema, se elige un nuevo símbolo no terminal, digamos B, y se hace lo siguiente.Agregar las reglas que contienen recursión a la izquierda de A →Aα1|Aα2|…|Aαr en B. Quedando las producciones de B de la siguiente manera: B→ α1|α2|…|αr| α1B|α2B|…|αrB

Posteriormente se reemplazan las producciones originales de A →Aα1|Aα2|…|Aαr| β1|β2|…|βs por las producciones libres de recursión a la izquierda. Quedando las producciones de A de la siguiente manera: A→ β1|β2|…|βs| β1B|β2B|…|βsB

Después de aplicar estos dos pasos la regla A →Aα1|Aα2|…|Aαr| β1|β2|…|βs quedará expresada en 2 reglas de la siguiente manera:Bà α1|α2|…|αr| α1B|α2B|…|αrB

Aà β1|β2|…|βs| β1B|β2B|…|βsB

Paso4. Convertir G en una gramática cuyas producciones sean de la forma A -> aα (donde α contiene varios símbolos no terminales).Cuando procesemos A, reemplazar todas las producciones A → Bα por A à β1α|...| βkα donde B→ β1α|...| βkα.

Paso5. Ahora la gramática ya casi está en FNG excepto porque hay algunas producciones de A -> aα donde α contienen algunos terminales. Para esto se introducen nuevos no terminales Qa por cada símbolo a, reemplazamos todas las ocurrencias erróneas con Qa y agregamos las producciones Qa -> a.

Definición. La recursión a la izquierda, es cuando hay una repetición del símbolo no terminal en la primera posición de la producción. Ejemplo: G → GaAS