En alguna ocasiones es posible transformar una Gramática en un otra debilmente equivalente, es decir que genera exactamente el mismo lenguaje pero con una estructura de árbol de derivación diferente. Alguna veces es algo conveniente porque los árboles de derivación de la nueva gramática podrían tener algunas propiedades de las cuales se podría tomar ventaja.

FNC #

Toda GLC se puede transformar en una gramática en la Forma Normal de Chomsky que requiere que las reglas tomen la siguiente forma:

Proceso de transformación #

Para transformar una gramática \((V,\Sigma,P,S)\) en su FNC se siguen los siguientes pasos:

0. Agregar un nuevo símbolo inicial \[ \begin{array}{ll} S_0 \rightarrow & S \\ \end{array} \]

1. Quitar las transiciones ε

   • Identificar las producción \( A \rightarrow \varepsilon \)
   • Producir nuevas producciones suponiendo que dónde aparece A es ε; por ejemplo si \( P \rightarrow AxB; A \rightarrow \varepsilon; B \rightarrow \varepsilon\) entonces se producen las nuevas reglas para P: \[ \begin{array}{ll} P \rightarrow & xB | Ax | x \\ \end{array} \]
   • Eliminar de la gramática las transiciones ε

2. Quitar las transiciones unitarias

   • Identificar las producción \( A \rightarrow B \)
   • Por cada \( B \rightarrow \alpha \) agregar las reglas: \[ \begin{array}{ll} A \rightarrow & \alpha \\ \end{array} \]
   • Eliminar de la gramática las unitarias

3. Quitar las transiciones largas

   • Identificar las producción \( A \rightarrow A_0A_1A_2\ldots A_m \)
   • Cortarlas usando símbolos auxiliares para encadenar la regla \[ \begin{array}{rl} A \rightarrow & A_0T_1 \\ T_1 \rightarrow & A_1T_2 \\ T_2 \rightarrow & A_2T_3 \\ \vdots \rightarrow & \vdots \\ T_{m-1}\rightarrow & A_{m-1}A_{m} \\ \end{array} \]

4. Quitar los terminales binarios

   • Identificar las producción \( A \rightarrow aB \)
   • Agregar una regla con el no terminal (si es necesario) y remplazar en la regla original la aparición del terminal con ese no terminal \[ \begin{array}{rl} A \rightarrow & N_aB \\ N_a \rightarrow & a \\ \end{array}\]

Ejemplo #

Reducir la siguiente gramática en su Forma Normal de Chomsky: \[ \begin{array}{rl} S \rightarrow & aSA | BSB | D\\ A \rightarrow & C \\ C \rightarrow & a \\ B \rightarrow & b \\ D \rightarrow & \varepsilon \\ \end{array}\]

0. Agregar un nuevo símbolo inicial \[ \begin{array}{lll} R_0 \rightarrow & S & \text{Nuevo símbolo}\\ S \rightarrow & aSA | BSB | D &\\ A \rightarrow & C &\\ C \rightarrow & a &\\ B \rightarrow & b &\\ D \rightarrow & \varepsilon & \\ \end{array} \]

1. Quitar las transiciones ε \[ \begin{array}{lll} R_0 \rightarrow & S | \varepsilon & \text{Se agregó por } S \rightarrow \varepsilon \\ S \rightarrow & aSA | BSB | aA | BB & \text{Se agrego por } B \rightarrow \varepsilon \\ A \rightarrow & C &\\ C \rightarrow & a &\\ B \rightarrow & b &\\ \end{array} \]

2. Quitar las transiciones unitarias \[ \begin{array}{lll} R_0 \rightarrow & S & \\ S \rightarrow & aSA | BSB | aA | BB & \\ A \rightarrow & a & \text{Se agrego por unitaria}\\ C \rightarrow & a &\\ B \rightarrow & b &\\ \end{array} \]

3. Quitar las transiciones largas \[ \begin{array}{lll} R_0 \rightarrow & S & \\ S \rightarrow & aT_1 | BV_1 | aA | BB & \text{Se redujeron por regla larga} \\ T_1 \rightarrow & SA & \text{Se creo por regla larga}\\ V_1 \rightarrow & SB & \text{Se creo por regla larga}\\ A \rightarrow & a & \\ C \rightarrow & a &\\ B \rightarrow & b &\\ \end{array} \]

4. Quitar los terminales binarios \[ \begin{array}{lll} R_0 \rightarrow & S & \\ S \rightarrow & N_aT_1 | BV_1 | N_aA | BB & \text{Se modifico por terminales binarios} \\ T_1 \rightarrow & SA &\\ V_1 \rightarrow & SB &\\ N_a \rightarrow & a & \text{Se creo por terminales binarios} \\ A \rightarrow & a & \\ C \rightarrow & a &\\ B \rightarrow & b &\\ \end{array} \]

Comparación de árboles de derivación #

La gramática original produce el siguiente árbol para la cadena abaaba

Mientras que la gramática resultante en FNC produce

Como se puede observar las dos cadenas son aceptadas, pero producen diferentes árboles de derivación. Una propiedad importante de la FNC es que cada rama del árbol sólo tiene dos hijos posibles.