Siguiente: Lenguajes libres de contexto Un nivel arriba: Formas normales Anterior: Forma normal de Chomsky

Forma normal de Greibach

Una gramática libre de contexto G=(V,T,P,S) se dice estar en forma normal de Greibach si sus producciones son de la forma

$$X\rightarrow a\sigma\ \ \mbox{\rm con }X\in V,a\in T,\sigma\in V^*.$$

Veremos que la construcción de formas normales de Greibach equivalentes a gramáticas dadas es procedimental. Para cualquier gramática libre de contexto G, definamos, para cada variable $X\in V$, a los conjuntos siguientes:

$$\begin{eqnarray*}P(X) &=&\{\mbox{\rm producciones en $G$\space cuyo antecedente ... ...ghtarrow\ \exists \xi\in (V+T)-\{X\},\gamma':\gamma=\xi\gamma' \end{eqnarray*}$$

Primeramente observemos que podemos ``componer producciones'' de manera que tengamos siempre una gramática equivalente a la gramática dada.

Lema 3.1 (Composición de producciones)   Si $(X\rightarrow \alpha_1Y\alpha_2)$ es una producción en G y las producciones en P(Y) pueden escribirse como $Y\rightarrow \beta_1\vert\cdots\vert\beta_m$ entonces al sustituir $(X\rightarrow \alpha_1Y\alpha_2)$ por las producciones $(X\rightarrow \alpha_1\beta_1\alpha_2\vert\cdots\vert\alpha_1\beta_m\alpha_2)$, obtenemos una gramática equivalente a G.

En efecto, en toda derivación terminal que aplique en un momento la producción $(X\rightarrow \alpha_1Y\alpha_2)$, necesariamente se ha de aplicar una producción en P(Y) para suprimir el símbolo Y.

Lema 3.2 (Transformación de producciones ``reflexivas'')   Para cada variable $X\in V$ enumeremos Q(X) y R(X) como

$$\begin{eqnarray*}Q(X) &=& \left(X\rightarrow X\gamma_1\vert\cdots\vert X\gamma_q... ...) &=& \left(X\rightarrow \beta_1\vert\cdots\vert\beta_r\right) \end{eqnarray*}$$

Sea Z una variable que no ocurra en V. Sea $G_X=\left(V\cup\{Z\},T,P_X,S)\right)$ la gramática que se obtiene al sustituir el conjunto de producciones P(X) por las producciones

$$\begin{array}{rcl} X &\rightarrow& \beta_1\vert\cdots\vert\b... ... &\rightarrow& \gamma_1Z\vert\cdots\vert\gamma_qZ \end{array}$$

En efecto, toda derivación siniestra, en la gramática original, de una palabra en L(G) ha de determinar una derivación diestra de la misma palabra en la gramática transformada. La demostración de la afirmación anterior es directa. Como mera ilustración, consideremos tan solo un ejemplo: La gramática con producciones $\{S\rightarrow SAb\vert b,\ A\rightarrow ASa\vert a\}$ genera al lenguaje consistente de las palabras de la forma b(ab)^*. De acuerdo con la construcción anterior, como $Q(S)=\{S\rightarrow SAb\}$ y $R(S)=\{S\rightarrow b\}$, obtenemos la gramática

$$\begin{array}{rcl} S &\rightarrow& b \\ S &\rightarrow& bZ \\ Z &\rightarrow& Ab \\ Z &\rightarrow& AbZ \end{array}$$

Presentemos sendas derivaciones, siniestra en la gramática original y diestra en la transformada, para la palabra bababab:

$$\begin{array}{\vert\vert c\vert\vert c\vert\vert}\hline \hlin... ...abab \\ bababab \end{array} \\ \hline \hline \end{array}$$

Veamos ahora el resultado principal de esta sección:

Proposición 3.2   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 Greibach.

Sea pues G=(V,T,P,S) una gramática libre de contexto que no genere a $\mbox{\it nil\/}$. La transformación a una forma normal de Greibach la hacemos gradualmente mediante los pasos siguientes:

1.

Sea G'=(V',T,P',S') la forma normal de Chomsky de G.

2.

Modificaremos a las producciones en P' para tenerlas tales que toda producción, cuyo consecuente se inicie con una variable, ha de ser de la forma $X_i\rightarrow X_j\sigma$ con j>i, para un cierto orden en el conjunto de variables actuales, digamos $V''=\{X_1,\ldots,X_m\}$. Para esto apliquemos el procedimiento cuyo seudocódigo se presenta en la figura 6.3.

  

Figure 6.3: Modificaciónde producciones de acuerdo con el orden de V'.

Por lo visto en el lema 6.3.2, la gramática G'' así obtenida es equivalente a G.

3.

Ahora, hecha la transformación anterior, se tiene que

• la última variable X_m sólo puede ser antecedente de producciones cuyos consecuentes se inician con símbolos terminales,
• las producciones en P(X_m-1) cuyos consecuentes se inician con X_m pueden transformarse, siguiendo el lema 6.3.1 de ``Composición de producciones'', en producciones equivalentes cuyos consecuentes se inician con símbolos terminales,
• de manera sucesiva para i=m-2 hasta i=1 las producciones en P(X<sub>i</sub>) cuyos consecuentes se inician con algún X<sub>j</sub>, con j>i, pueden transformarse, siguiendo el lema 6.3.1 de ``Composición de producciones'', en producciones equivalentes cuyos consecuentes se inician con símbolos terminales.

Con todas estas transformaciones la gramática resultante G^*=(V^*,T,P^*,S^*) es, en efecto, equivalente a G y está en forma normal de Greibach.

Ejemplo:

Consideremos la gramática con símbolos variables $V=\{X_1,X_2,X_3\}$ y producciones
$\begin{array}{lrcl} 1. & X_1 &\rightarrow& X_2X_3 \\ 2. & X_2 &\rightarrow& X_3X_1\vert b \\ 3. & X_3 &\rightarrow& X_1X_2\vert a \end{array}$
la cual ya está en forma normal de Chomsky. Transformémosla de acuerdo con el procedimiento anterior. Observemos que las dos primeras producciones ya tienen el tipo de las buscadas en el paso 2. del procedimiento anterior. La tercera tiene un consecuente que se inicia con un símbolo variable anterior al de su propio antecedente. Compongamos pues la producción 3. con la 1. Obtenemos
$\begin{array}{lrcl} 4. & X_3 &\rightarrow& X_2X_3X_2\vert a \end{array}$
la cual también tiene un consecuente que se inicia con un símbolo variable anterior al de su propio antecedente. Compongamos pues la producción 4. con la 2. Obtenemos
$\begin{array}{lrcl} 5. & X_3 &\rightarrow& X_3X_1X_3X_2\vert bX_3X_2\vert a \end{array}$
la cual es del tipo ``reflexivo''. Para transformarla, introduzcamos una nueva variable Y₃. Obtenemos
$\begin{array}{lrcl} 6. & X_3 &\rightarrow& bX_3X_2Y_3\vert aY_3\vert bX_3X_2\vert a \\ 7. & Y_3 &\rightarrow& X_1X_3X_2Y_3\vert X_1X_3X_2 \end{array}$ Con esto terminamos el paso 2. del procedimiento anterior. El conjunto actual de producciones consta de las producciones 1., 2., 6. y 7. Pasemos pues al paso 3. del procedimiento. Sustituyendo 6. en 2. obtenemos
$\begin{array}{lrcl} 8. & X_2 &\rightarrow& bX_3X_2Y_3X_1\vert aY_3X_1\vert bX_3X_2X_1\vert aX_1\vert b \end{array}$ Sustituyendo 8. en 1. obtenemos
$\begin{array}{lrcl} 9. & X_1 &\rightarrow& bX_3X_2Y_3X_1X_3\vert aY_3X_1X_3\vert bX_3X_2X_1X_3\vert aX_1X_3\vert bX_3 \end{array}$ Sustituyendo 9. en 7. obtenemos 10 nuevas producciones
$\begin{array}{lrcl} 7. & Y_3 &\rightarrow& \begin{array}[t]{rr}\begin{array}[t... ...ert \\ aX_1X_3X_3X_2\vert \\ bX_3X_3X_2 \ \end{array}\end{array} \end{array}$ En resumen, la gramática equivalente, en forma normal de Greibach, tiene como conjunto de variables a $V=\{X_1,X_2,X_3,Y_3\}$ y sus producciones son la 6., 8., 9. y 10.:

$$\begin{eqnarray*}X_1 &\rightarrow& bX_3X_2Y_3X_1X_3\vert aY_3X_1X_3\vert bX_3X_2... ... \\ aX_1X_3X_3X_2\vert \\ bX_3X_3X_2 \ \end{array}\end{array} \end{eqnarray*}$$

Ejemplo ``Cadenas equilibradas de paréntesis'':

Consideremos la gramática $S\rightarrow ()\vert SS\vert(S)$ que genera a las cadenas equilibradas de paréntesis (CEP). La forma normal de Chomsky de la gramática dada es
$\begin{array}{llcl} 1. & S &\rightarrow& SS\vert P_{\mbox{\scriptsize\it Izq}}... ...arrow& ) \\ 4. & A &\rightarrow& SP_{\mbox{\scriptsize\it Der}} \end{array}$ Consideremos el siguiente orden de las variables: $S,A,P_{\mbox{\scriptsize\it Izq}},P_{\mbox{\scriptsize\it Der}}$. La producción 1. es ``reflexiva''. Introduzcamos una nueva variable, X₁. Al hacer la transformación pertinente, obtenemos:
$\begin{array}{llcl} 5. & S &\rightarrow& P_{\mbox{\scriptsize\it Izq}}P_{\mbox... ...box{\scriptsize\it Izq}}A \\ 6. & X_1 &\rightarrow& SX_1\vert S \end{array}$ La producción 4. tiene un consecuente que se inicia con una variable anterior a su antecedente. Al componer 4. con 5. obtenemos
$\begin{array}{llcl} 7. & A &\rightarrow& P_{\mbox{\scriptsize\it Izq}}P_{\mbox... ...\vert P_{\mbox{\scriptsize\it Izq}}AP_{\mbox{\scriptsize\it Der}} \end{array}$ La producción 6. tiene un consecuente que se inicia con una variable anterior a su antecedente. Al componer 6. con 5. obtenemos
$\begin{array}{llcl} 8. & X_1 &\rightarrow& \begin{array}[t]{rr}\begin{array}[t... ...\vert \\ P_{\mbox{\scriptsize\it Izq}}A \ \end{array}\end{array} \end{array}$ Al componer 8. con 2. obtenemos
$\begin{array}{llcl} 9. & X_1 &\rightarrow& \begin{array}[t]{rr}\begin{array}[t... ..._{\mbox{\scriptsize\it Der}}\vert \\ (A \ \end{array}\end{array} \end{array}$ En este momento, en nuestro conjunto actual de producciones 2., 3., 5., 7. y 9., ningún consecuente se inicia con alguna variable que anteceda a la variable en el antecedente de la producción correspondiente. En el paso 3. del procedimiento para obtener formas normales de Greibach, hemos de sustituir la variable $P_{\mbox{\scriptsize\it Izq}}$ por el símbolo (, según la producción 2., toda vez que aparezca al inicio del consecuente de alguna producción. Obtenemos así la gramática:

$$\begin{eqnarray*}P_{\mbox{\scriptsize\it Izq}} &\rightarrow& ( \\ P_{\mbox{\sc... ...mbox{\scriptsize\it Der}}\vert \\ (A \ \end{array}\end{array} \end{eqnarray*}$$

Y esta gramática ya queda en forma normal de Greibach. Observemos que la variable $P_{\mbox{\scriptsize\it Izq}}$ es irrelevante. De hecho si hacemos la sustitución del otro símbolo $P_{\mbox{\scriptsize\it Der}}$ obtenemos la gramática equivalente

$$\begin{eqnarray*}S &\rightarrow& ()X_1\vert(AX_1\vert()\vert(A \\ A &\rightarr... ...\vert \\ (AX_1\vert \\ ()\vert \\ (A \ \end{array}\end{array} \end{eqnarray*}$$

que también está en forma normal de Greibach.
Siguiente: Lenguajes libres de contexto Un nivel arriba: Formas normales Anterior: Forma normal de Chomsky