Una producción vacía o producción-
es una producción de la forma
.
Proposición 2.2
Toda gramática libre de contexto
G=(V,T,P,S) se puede transformar en una gramática libre de contexto
G'=(V',T,P',S') sin variables inútiles ni producciones vacías que es casi equivalente a G, i.e.
:
En efecto, dada una gramática G evitemos las producciones vacías. Definamos a las variables anulables de manera recursiva como sigue:
Si
es una producción vacía entonces X es anulable.
Si
son anulables y
es una producción en la gramática entonces X es anulable.
Sea
y sea P'' el conjunto de producciones construído a partir de P como sigue:
Para cada producción en P de la forma
y para cada
hagamos Yi=Xi si
y
si
.
Si
entonces incorporemos la producción
al conjunto P''.
Sea G' la gramática que se obtiene de suprimir símbolos inútiles en G''. G' es la gramática cuya existencia se proclama en la proposición.
Guillermo Morales-Luna
2000-06-27