Siguiente: Formas normales Un nivel arriba: Transformaciones equivalentes de gramáticas Anterior: Supresión de producciones vacías

Supresión de producciones unitarias

Una producción unitaria es una de la forma $X\rightarrow Y$ con $X,Y\in V$.

Proposición 2.3   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') sin variables inútiles ni producciones vacías ni producciones unitarias equivalente a G.

En efecto, dada una gramática G, construyamos, mediante la construcción anterior, la gramática G' equivalente a G sin variables inútiles ni producciones vacías. Si hubiese aún producciones unitarias podríamos acomodarlas todas en una lista como la siguiente:

$$\begin{array}{ccccccc} Y_{11} &\rightarrow & Y_{12} &\righta... ...m2} &\rightarrow & \cdots &\rightarrow & Y_{mk_m} \end{array}$$

Así pues $\forall i\leq m\forall 1\leq j\leq l\leq k_i:\ Y_{ij}\stackrel{*}{\rightarrow} Y_{il}$. Pues bien, ahora para cada par de producciones $X\stackrel{*}{\rightarrow} Y$, $Y\rightarrow \sigma$ con $X,Y\in V,\sigma\in (V+T)^*$, a esas producciones las sustituimos por la producción $X\rightarrow \sigma$. La gramática G' que así obtenemos es equivalente a G'', y por tanto a G, y es como la anunciada en la proposición.