Forma Normal de Chomsky y Greibach

Forma Normal de Chomsky (FNC)
Sea una gramática con y un símbolo no-terminal (o una variable). Podemos clasificar tales símbolos en tres clases:
variables accesibles:
si existe una derivación desdeel símbolo inicial que contiene , es decir, existe donde .
variables generativas:
si existe una derivación desde el la variable que produce una sentencia , es decir, existe donde .
variablesútiles:
si existe una derivación desde el símbolo inicial usando que produce una sentencia , es decir, existe donde y .
Una gramática está en forma normal de Chomsky (FNC)
si (es decir, su ) solamentecontiene variables útiles y
si todas las producciones de (es decir, en su ) son
o bien de la forma con
o bien de la forma con y
si (es decir, el símbolo inicial de ) no aparece al lado derecho deninguna producción, también está permitido que .
La tercera condición es necesaria para poder derivar . Si aparece a la derecha, primero habrá que sustituir las producciones implicadas adecuadamente comolo vimos en la conversión de una gramática lineal por la derecha a una gramática lineal por la izquierda.
Observamos:
la primera condición garantiza que todas las variables son necesarias paraderivar por lo menos una sentencia.
la segunda condición garantiza que un árbol de derivación es un árbol binario.
Obviamente cualquier gramática en forma normal de Chomsky es una gramática libre decontexto que se verifica directamente analizando la forma de producciones permitidas.
Pero también es valido la otra dirección: para cualquier lenguaje libre de contexto existe una gramática en formanormal de Chomsky, que genera el mismo lenguaje.
La comprobación de este hecho detallamos con la siguiente construcción donde a partir de una gramática libre de contexto dada, elaboramos una nuevagramática en forma normal de Chomsky.
Sea un lenguaje libre de contexto y una gramática que genere (es decir ).
Forma Normal de Greibach (FNG)
Veremos otra posible normalización de gramáticas que nos...