Forma Normal de Greibach

Veremos otra posible normalización de gramáticas que nos sirve más adelante para construir cierto tipo de autómatas.

Una gramática es en forma normal de Greibach (FNG) si

• $G$ (es decir, su $\Sigma_N$) solamente contiene variables útiles
• todas las producciones de $G$ (es decir, en su $P$) son de la forma $X\longrightarrow \sigma\Upsilon$ donde $\sigma\in\Sigma_T$ y $\Upsilon\in\Sigma_N^*$, es decir, todas las reglas tienen como primer símbolo en sus partes derechas un símbolo terminal que es seguido por una palabra de variables.
• (porque así no se podría derivar $\epsilon$) si $\$ (es decir, el símbolo inicial de $G$) no aparece al lado derecho de una producción, también está permitido que $\$\longrightarrow \epsilon\in P$

Obviamente cualquier gramática en forma normal de Greibach es una gramática libre de contexto que se verifica directamente analizando la forma de producciones permitidas.

Una interesante propiedad es: para cualquier lenguaje libre de contexto existe una gramática en forma normal de Greibach, que genera el 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 nueva gramática en forma normal de Greibach.

Sea $L$ un lenguaje libre de contexto y $G=(\Sigma_N,\Sigma_T,P,\$)$ una gramática que genere $L$ (es decir $L=L(G)$).

La construcción sigue 4 pasos (asumimos que $\epsilon\notin L$, eso remediamos al final):

1. construimos una gramática equivalente en forma normal de Chomsky
2. sustituimos las reglas recursivas a la izquierda, es decir, reglas de tipo $X\longrightarrow XY$
3. establecemos un orden en las variables, es decir $\Sigma_N=\{X_1,X_2,\dots,X_n\}$ de tal manera que todas las reglas serán de tipo $X_i\longrightarrow X_jY$ con $i<j$, $Y\in\Sigma_N$
4. sustituimos las reglas que no tengan un símbolo terminal como primer símbolo en su parte derecha.

Las gramáticas después de cada paso llamamos $G=G_0,G_1,G_2,\dots,G_4=G_{FNG}$ respectivamente.

Usamos la misma gramática inicial como en el apartado anterior

$$G_0=(\{\$,A,B,C,D,E,F\},\{a,b,c\},P_0,\$)$$

donde $P_0$ contenga las siguientes producciones:

$$\begin{eqnarray*} \$ &\longrightarrow & bDD\;\vert\;Ca\;\vert\;bc \\ A &\longri... ...;\vert\;EF \\ E &\longrightarrow & Eb\\ F &\longrightarrow & a \end{eqnarray*}$$

como ejemplo para realizar todos los pasos.

1. La transformación a FNC hicimos arriba. Entonces ya tenemos $P_1$ como
   $$\begin{eqnarray*} \$ &\longrightarrow & CW_a\;\vert\;W_b\$_1\;\vert\;W_bW_c \\ ... ...tarrow &a\\ W_b&\longrightarrow &b\\ W_c&\longrightarrow &c\\ \end{eqnarray*}$$
   
   
   solo reordenado, para que aparezcan las partes derechas con variables al principio al comienzo de las listas.
2. Para cada producción recursiva a la izquierda, es decir, regla de tipo $X\longrightarrow X\alpha$ con $X\in\Sigma_N$ y $\alpha\in\Sigma$ se realiza los siguientes 3 pasos:
   • se sustitue $X\longrightarrow X\alpha$ por $X\longrightarrow \alpha Y$ siendo $Y$ una nueva variable
   • se añade las reglas $Y\longrightarrow \alpha Y\;\vert\;\alpha$
   • para cada regla $X\longrightarrow \beta$ se añade $X\longrightarrow \beta Y$ si $\beta$ no comienza con $X$

   En $P_1$ hay una regla recursiva a la izquierda: $A\longrightarrow AC$. Entonces, la sustituimos por $A\longrightarrow CA_3$, añadimos $A_3\longrightarrow CA_3\;\vert\;C$ y añadimos las demás reglas para $A$, y resulta el conjunto $P_2$:

   $$\begin{eqnarray*} \$ &\longrightarrow & CW_a\;\vert\;W_b\$_1\;\vert\;W_bW_c \\ ... ...tarrow &a\\ W_b&\longrightarrow &b\\ W_c&\longrightarrow &c\\ \end{eqnarray*}$$
   
   
   Entonces las reglas en $P_2$ tienen de nuevo diferentes longitudes en sus partes derechas (incluso puede ser que haya reglas unitarias).

3. (por incluir)
4. (por incluir)

Dado que con una gramática en forma normal de Greibach se genera con cada producción exactamente un símbolo terminal, cada palabra derivable con tal gramática tiene una derivación igual a la longitud de la palabra.

Ojo, eso no significa que se puede encontrar una derivación en tiempo lineal, porque es posible que en un momento se puede aplicar más de una regla.