Forma normal de chomsky

Forma Normal de Chosmky la Forma Normal de Greibach
Idea Principal.

La jerarquía de Chomsky indica cual debe ser el formato general que cumplan las producciones de
una gramática para generar un lenguaje de una determinada clase. Pero ese formato es tan general que da lugar a múltiples formas gramaticales posibles para las producciones. Especialmente, en el caso de las GCLs.
Una forma normales un intento de estandarizar las producciones y conseguir que todas tengan una
apariencia similar. Esa serıa la primera idea. Pero tienen más utilidades. En la asignatura se estudian dos formas normales distintas para las GCLs: la forma normal de Chomsky (FNCh) y la forma normal de Greibach (FNG). En ambos casos se debe partir de un GCL ya simplificada.

Forma Normal de Chomsky.
La teoríadefine así la FNCh:
“Todo LCL L, _ 62 L, se puede generar por una GCL en la que todas sus producciones
tienen el siguiente formato:
A ! BC
A ! a
donde A, B, C son símbolos auxiliares y a es un símbolo terminal”.
Para entender el porqué de esta forma normal, además de por sus aplicaciones prácticas (por ejemplo, para ver si el lenguaje generado por una GCL es o no es finito), hay que recordarque Chomsky es lingüista y. aun mas, es el padre de la teoría generativa, que dice que el ser humano nace con unas estructuras gramaticales innatas. Llego a esta conclusión tras analizar la estructura similar de muchos lenguajes que, aparentemente, son muy diferentes. Pero casi todos comparten frases con una estructura de hSUJETO PREDICADOi (hmmm... un par de auxiliares) y, a su vez, cada una deestas partes comparte un estructura de tipo hNUCLEO COMPLEMENTO Si (¡vaya! otro par de auxiliares...) y si se sigue el análisis se ve que, por ejemplo, el NU CLEO del PREDICADO es un verbo (caramba, Vamos que NUCLEO! verbo, o sea que un auxiliar se deriva en un terminal... curioso).

Bien, sea como sea, para obtener la FNCh hay que seguir dos pasos. Primero, si se observan los
dos formatospermitidos, se ve que no se pueden mezclar símbolos auxiliares y símbolos terminales en una misma producción. Para conseguir eso, se definen tantos auxiliares como haga falta para substituir a los terminales que aparezcan mezclados con auxiliares en los consecuentes de las producciones. En el ejemplo, el efecto será:

Como se ve, puesto que a y b aparecían mezclados con auxiliares en distintasproducciones, por
ejemplo (S ! ABa) ´o (B ! Ab), se han definido dos nuevos auxiliares, Ca y Cb cuyas únicas producciones son (Ca ! a) y (Cb ! b). Al substituir, por ejemplo (S ! ABCa) ´o (B ! ACb), desaparecen las “mezclas”. Ojo, que en producciones como (S ! a) ´o (A ! a) no hay que substituir, ya estan en forma normal de Chomsky.
Una vez obtenida esta forma “pseudo-Chomsky”, se aplica el segundopaso, que tiene que ver con
Que el único formato permitido en producciones de auxiliares es por parejas. Por lo tanto, en todas las producciones que aparezcan más de dos símbolos auxiliares hay que conseguir una agrupación que permita cumplir con esta regla. En el ejemplo se podría pensar en lo siguiente:

Se ha agrupado el par de auxiliares BCa y se introduce un nuevo auxiliar cuya únicaproducción sea (X ! BCa). Con substituir todas las apariciones del par BCa por el nuevo auxiliar X se eliminan casi todos los tríos de auxiliares. Para eliminar el trio AAA se hace algo similar, introduciendo el auxiliar Y . Nótese que solo se utiliza Y para transformar (S ! AAA) en (S ! AY ); sobre la producción (S ! AA) no se aplica la substitución porque ya está en forma de Chomsky.

Forma Normalde Greibach

Veremos otra posible normalización de gramáticas que nos sirve más adelante para construir cierto tipo de autómatas.
Una gramática es en forma normal de Greibach (FNG) si
* (es decir, su ) solamente contiene variables útiles
* todas las producciones de (es decir, en su ) son de la forma donde y , es decir, todas las reglas tienen como primer símbolo en sus partes...