5.4 - Formas normales de Chomsky.

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

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.

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