Siguiente: Supresión de producciones unitarias Un nivel arriba: Transformaciones equivalentes de gramáticas Anterior: Supresión de símbolos inútiles

Supresión de producciones vacías

Una producción vacía o producción- $\mbox{\it nil\/}$ es una producción de la forma $X\rightarrow \mbox{\it nil\/}$.

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. $L(G')=L(G)-\{\mbox{\it nil\/}\}$:

$$\forall \sigma\in T^*-\{\mbox{\it nil\/}\}:\ \left(\sigma\in L(G')\ \Leftrightarrow\ \sigma\in L(G)\right).$$

En efecto, dada una gramática G evitemos las producciones vacías. Definamos a las variables anulables de manera recursiva como sigue:

• Si $X\rightarrow \mbox{\it nil\/}$ es una producción vacía entonces X es anulable.
• Si $X_1,\ldots,X_k$ son anulables y $X\rightarrow X_1\cdots X_k$ es una producción en la gramática entonces X es anulable.

Sea $V''=V-\{X\in V\vert X \mbox{\rm es anulable}\}$ y sea P'' el conjunto de producciones construído a partir de P como sigue: Para cada producción en P de la forma $X\rightarrow X_1\cdots X_k$ y para cada $i\leq k$ hagamos Y_i=X_i si $X_i\in V''$ y $Y_i=\mbox{\it nil\/}$ si $X_i\not \in V''$. Si $Y_1\cdots Y_k\not=\mbox{\it nil\/}$ entonces incorporemos la producción $Y\rightarrow Y_1\cdots Y_k$ 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.