Forma Normal de Chomsky

Sea $G=(\Sigma_N,\Sigma_T,P,\$)$ una gramática con $P\subset\Sigma_N\times(\Sigma_N\cup\Sigma_T)^*$ y $X\in\Sigma_N$ un símbolo no-terminal (o una variable). Podemos clasificar tales símbolos $X$ en tres clases:

variables acesibles:

si existe una derivación desde el símbolo inicial que contiene $X$, es decir, existe $\$\longrightarrow ^*\alpha X\beta$ donde $\alpha,\beta\in\mbox{$\Sigma^*$}$.

variables generativas:

si existe una derivación desde el la variable que produce una sentencia $w$, es decir, existe $X\longrightarrow ^*w$ donde $w\in\Sigma_T^*$.

variables útiles:

si existe una derivación desde el símbolo inicial usando $X$ que produce una sentencia $w$, es decir, existe $\$\longrightarrow ^*\alpha X\beta\longrightarrow ^*w$ donde $\alpha,\beta\in\mbox{$\Sigma^*$}$ y $w\in\Sigma_T^*$.

Una gramática está en forma normal de Chomsky (FNC)

• si $G$ (es decir, su $\Sigma_N$) solamente contiene variables útiles y
• si todas las producciones de $G$ (es decir, en su $P$) son
  • o bien de la forma $X\longrightarrow YZ$ con $X,Y,Z\in\Sigma_N$
  • o bien de la forma $X\longrightarrow \sigma$ con $X\in\Sigma_N$ y $\sigma\in\Sigma_T$
• si $\$ (es decir, el símbolo inicial de $G$) no aparece al lado derecho de ninguna producción, también está permitido que $\$\longrightarrow \epsilon\in P$.

La tercera condición es necesaria para poder derivar $\epsilon$. Si $\$ aparece a la derecha, primero habrá que sustituir las producciones implicadas adecuadamente como lo vimos en la conversión de una gramática lineal por la derecha a una gramática lineal por la izquierda.

Observamos:

• la primera condición garantiza que todas las variables son necesarias para derivar por lo menos una sentencia.
• la segunda condición garantiza que un árbol de derivación es un árbol binario.

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

Pero también es valido la otra dirección: para cualquier lenguaje libre de contexto existe una gramática en forma normal de Chomsky, que genera el mismo 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 Chomsky.

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 5 pasos (asumimos que $\epsilon\notin L$, eso remediamos al final):

1. eliminamos las variables inútiles
2. modificamos las reglas para que no haya mezcla de variables y constantes en las partes derechas de las producciones y para que todas las reglas con constantes tengan la forma $X\longrightarrow \sigma$
3. sustituimos las reglas cuya longitud de su parte derecha es $>2$
4. sustituimos las reglas de tipo $X\longrightarrow \epsilon$
5. sustituimos las reglas de tipo $X\longrightarrow Y$, las reglas unitarias.

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

Usamos la siguiente gramática inicial

$$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. Sabiendo que una variable es inútil si es no-generativa o inacesible realizamos dos subpasos:
   1. eliminamos primero las variables no-generativas $N$ (y todas las reglas con ellas) llamando a la gramática resultante $G_1^\prime$,
   2. eliminamos después las variables inacesibles $I$ (y todas las reglas con ellas).
   Para ello recorremos en forma estructurada las variables y reglas:
   1. para calcular $N$ empezamos con aquellas variables que producen directamente sentencias (incluyendo $\epsilon$) y seguimos el uso de reglas con dichas variables para producir así sucesivamente sentencias (o en otras palabras: `seguimos las reglas desde el lado derecho hacia el lado izquierdo para obtener así la información sobre las variables').

      Una forma de realizar dicho recorrido es empezar con $N=\Sigma_N$ y borrar del conjunto todas aquellas variables que o bien directamente deriven una sentencia o bien lo hacen indirectamente.

      Se observa que solamente $E$ es un símbolo no-generativo, es decir, $N=\{E\}$, $P_1^\prime$ entonces es:

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

   2. para calcular $I$ empezamos con el símbolo inicial y veremos a cuales de las variables se puede llegar directamente y seguimos el uso de reglas con dichas variables para llegar así sucesivamente a nuevas variables (o en otras palabras: `seguimos las reglas para obtener así la información sobre las variables acesibles'). Dicho algoritmo es una exploración de un grafo de dependencia parecido al algoritmo que vimos para detectar estados no-acesibles en un autómata finito.

      Se observa que solamente $F$ es un símbolo inacesible, es decir, $I=\{F\}$, $P_1$ entonces es:

      $$\begin{eqnarray*} \$ &\longrightarrow & bDD\;\vert\;Ca\;\vert\;bc \\ A &\longri... ...tarrow & bD\;\vert\;aBA\\ D &\longrightarrow & CD\;\vert\;a \\ \end{eqnarray*}$$
      
      

   Entonces $G_1$ no contiene símbolos inútiles.

2. Añadimos para cada símbolo terminal $\sigma$ una regla $W_\sigma$ y sustituimos $\sigma$ en todas las reglas de $P_1$, $P_2$ entonces es:
   $$\begin{eqnarray*} \$ &\longrightarrow & W_bDD\;\vert\;CW_a\;\vert\;W_bW_c \\ A ... ...tarrow &a\\ W_b&\longrightarrow &b\\ W_c&\longrightarrow &c\\ \end{eqnarray*}$$
   
   
   Entonces $P_2$ solamente contiene reglas con partes derechas siendo $\epsilon$, un símbolo terminal, o una palabra de variables.

3. Sustituimos cada regla del tipo $X\longrightarrow Y_1Y_1\dots Y_k$ con $k>2$ por las reglas:
   $$\begin{eqnarray*} X&\longrightarrow &Y_1X_1\\ X_1&\longrightarrow &Y_2X_2\\ \v... ...tarrow &Y_{k-2}X_{k-2}\\ X_{k-2}&\longrightarrow &Y_{k-1}Y_k\\ \end{eqnarray*}$$
   
   
   donde las $X_i$ son nuevas variables, $P_3$ entonces es:
   $$\begin{eqnarray*} \$ &\longrightarrow & W_b\$_1\;\vert\;CW_a\;\vert\;W_bW_c \\ ... ...tarrow &a\\ W_b&\longrightarrow &b\\ W_c&\longrightarrow &c\\ \end{eqnarray*}$$
   
   
   Entonces $P_3$ solamente contiene reglas con partes derechas siendo $\epsilon$, un símbolo terminal, o una palabra de una o dos variables.

4. Eliminamos las reglas que producen $\epsilon$, ¡ojo! tenemos que distinguir entre variables que solamente producen $\epsilon$ y aquellas que también producen $\epsilon$.

   Entonces, el paso se realiza en 3 partes:

   • Calculamos los conjuntos de variables
     $E=\{V\;\vert\;V\longrightarrow ^*\epsilon\}$ (las variables que posiblemente producen $\epsilon$) y
     $E_\epsilon=\{V\;\vert\;V\longrightarrow ^*\epsilon \mbox{ y no existe } V\longrightarrow ^*w \mbox{ con } w\not=\epsilon\} \subset E$ (las variables que solo producen $\epsilon$).

     Se calculan los conjuntos aplicando el mismo algoritmo que usamos en el primer paso para detectar variables no-generativas.

   • Añadimos para cada regla del tipo $X\longrightarrow YZ$
     • $X\longrightarrow Y$ si $Y\notin E_\epsilon$ y $Z\in E$
     • $X\longrightarrow Z$ si $Y\in E$ y $Z\notin E_\epsilon$.
   • Eliminamos
     • todas las reglas de tipo $X\longrightarrow \epsilon$,
     • todas las reglas de tipo $X\longrightarrow Y$ con $Y\in E_\epsilon$, y
     • todas las reglas de tipo $X\longrightarrow YZ$ con $Y,Z\in E_\epsilon$.

   En el ejemplo tenemos: $E=\{A,B,C_1\}, E_\epsilon=\emptyset$, y por eso $P_4$ es:

   $$\begin{eqnarray*} \$ &\longrightarrow & W_b\$_1\;\vert\;CW_a\;\vert\;W_bW_c \\ ... ...tarrow &a\\ W_b&\longrightarrow &b\\ W_c&\longrightarrow &c\\ \end{eqnarray*}$$
   
   

5. Para eliminar las reglas unitarias, es decir, reglas de tipo $X\longrightarrow Y$ procedemos:
   • Calculamos el conjunto de las reglas unitarias $U=\{(X,Y)\;\vert\;X\longrightarrow ^*Y\}$ (¡ojo! no basta con $(X,Y)\in U$ si $X\longrightarrow Y$, hay que calcular la clausura transitiva). Dicho cálculo se realiza de forma parecida como lo vimos para el cálculo de la clausura transitiva de las transiciones $\epsilon$ en los AFND-$\epsilon$.

     Partimos del conjunto que contiene todas las reglas unitarias del sistema de producciones, es decir
     

     $$U_1=\{(X,Y)\vert X\longrightarrow Y \in P\}$$
     
     
     Después construimos $U_2$ insertando para cada par de parejas $(X,Y),(Y,Z)\in U_1$ la pareja $(X,Z)$, o en general, construimos $U_i$ insertando para cada par de parejas $(X,Y),(Y,Z)\in \bigcup_{j<i} U_j$ la pareja $(X,Z)$.

     Seguimos con el procedimiento hasta que encontramos $U_i$ vacía para cierto $i$, es decir, no se ha añadido nada más. (El índice $i$ de $U_i$ nos indica con cuantos `saltos' como mucho podemos llegar.) El algoritmo termina (porque el número de producciones es finito) y finalmente obtenemos
     

     $$U=\bigcup_{i=1}^\infty U_i$$
     
     

     Nota: El cálculo de la clausura transitiva en un grafo dirigido es una operación que se necesita en muchos ámbitos de la informática (por ejemplo en bases de datos relacionadas). Nosotros ya lo usamos en el contexto de los autómatas finitos. El algoritmo especificado arriba tiene un tiempo de ejecución cuadrático en el número de producciones iniciales. Los mejores algoritmos tienen un comportamiento de $O(ne+n+e)$ en tiempo de ejecución (donde $n$ es el número de nodos y $e$ el número de aristas en el grafo), pero algunos de ellos se comportan en casos prácticos linealmente respecto al tamaño de entrada (número de arista).

   • Para cada $(X,Y)\in U$ y para cada regla $Y\longrightarrow \alpha$ que no es regla unitaria, añadimos una regla $X\longrightarrow \alpha$.
   • Eliminamos todas las reglas unitarias.
   $$\begin{eqnarray*} \$ &\longrightarrow & W_b\$_1\;\vert\;CW_a\;\vert\;W_bW_c \\ ... ...tarrow &a\\ W_b&\longrightarrow &b\\ W_c&\longrightarrow &c\\ \end{eqnarray*}$$
   
   
   En el ejemplo tenemos:
   $$\begin{eqnarray*} U_1&=&\{(A,B),(B,C),(B_1,D),(C,W_a),(C_1,A),(C_1,B),(D,W_a)\}\... ...W_a),(C_1,C)\}\\ U_3&=&\{(A,W_a),(C_1,W_a)\}\\ U_4&=&\emptyset \end{eqnarray*}$$
   
   
   y por eso $P_5$, el sistema de producciones final, queda en:
   $$\begin{eqnarray*} \$ &\longrightarrow & W_b\$_1\;\vert\;CW_a\;\vert\;W_bW_c \\ ... ...tarrow &a\\ W_b&\longrightarrow &b\\ W_c&\longrightarrow &c\\ \end{eqnarray*}$$
   
   

Observamos en la construcción:

• En ningún paso hemos añadido variables inútiles.
• Si hemos borrado reglas, hemos asegurado que todas las variables siguen siendo útiles.
• Después de cada paso la gramática resultante genera el mismo lenguaje, es decir, $L(G_0)=L(G_1)=\dots=L(G_5)$.
• Como se observa, la gramática $G_5$ es en forma normal de Chomsky.

Si el lenguaje de partida $L$ contiene la palabra vacía ($\epsilon\in L$) entonces se detecta en el pasa 4 que el símbolo inicial pertenece a $E$ (o incluso a $E_\epsilon$), en este caso eliminamos con un nuevo símbolo, por ejemplo $\$^\prime$, la aparencia de $\$ en los lados derechos y añadimos la regla $\$\longrightarrow \epsilon$. Tal gramática sigue estando en forma normal de Chomsky y genera $L$.

Notas:

• El cálculo de los conjuntos $N$, $I$, $E$, $E_\epsilon$, y $U$ que se necesitan para sucesivamente modificar los sistemas de producciones se realiza con un recorrido estructurado sobre las variables y producciones.
• Dado que durante el proceso hemos eliminado producciones, puede ser que también en el alfabeto de los símbolos terminales $\Sigma_T$ hay símbolos superfluos, es decir, que no se pueden producir con las producciones restantes. Dichos símbolos se pueden borrar de $\Sigma_T$ sin que se cambie el lenguaje generado.
• Cuando eliminamos las reglas unitarias hemos eliminado implíctamente las reglas innecesarias de tipo $X\longrightarrow X$ que también se podría borrar ya antemano en un paso previo.
• Existen otras fuentes que primero realizan la eliminación de las reglas nulas y de las reglas unitarias antes de demezclar y reducir las partes derechas de las reglas. Eso es posible pero el cálculo de $E$ y $E_\epsilon$ es más complejo y las reglas de ampliación y eliminación no se limitan a dos, respectivamente tres, casos simples como descritos arriba en el paso 4.