Diremos que una gramática incontextual G=(N,T,P,S) que no genera la cadena vacía,
está en FNC cuando todas sus reglas son de la forma:
A → BC con A,B,C ∈ N
A → a, con A,B ∈ N y a ∈T
Teorema. Todo lenguaje incontextual L que no incluye
la cadena vacía, es generado por una gramática en FNC
Una gramática
libre de contexto G=(N,T,P,S) se dice estar en forma normal de Chomsky si sus
producciones son de cualquiera de las dos formas:
Toda
gramática libre de contexto G=(V,T,P,S) que no genere a la palabra vacía se
puede transformar en una gramática libre de contexto G'=(V',T,P',S') en forma
normal de Chomsky.
En
efecto, dada una gramática G, apliquemos el último procedimiento de la sección
anterior para transformar a G en una gramática G'' sin variables inútiles ni
producciones vacías ni producciones unitarias equivalente a G. A las
producciones que quedasen de la forma con y las dejamos sin cambio alguno. A
cada producción de la forma , con y , la transformamos en una sucesión de
producciones de la forma siguiente: A cada símbolo terminal que aparezca en la
palabra le asociamos una variable nueva Xa e incorporamos la producción . Así
pues las producciones que no sean de la forma con X variable y a terminal, han
de ser de la forma , con todos variables. Para cada una de estas últimas
producciones introducimos k-2 nuevas variables e incorporamos la sucesión de producciones.
Pasos para 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
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
