Convertir una gramatica de expresiones aritmeticas a forma normal de Chomsky

Convertir a Forma Normal de Chomsky significa que cada regla debe tener exactamente la forma $A \to BC$ (dos no terminales) o $A \to a$ (un terminal). La gramatica original de expresiones aritmeticas ya no tiene producciones epsilon ni unitarias, asi que solo necesitamos dos transformaciones.

Primero, en cualquier regla con dos o mas simbolos que mezcle terminales, reemplazamos cada terminal por un nuevo no terminal dedicado. Por ejemplo, $+$ se reemplaza por $C_+$ (con $C_+ \to +$), $*$ por $C_*$, y asi con parentesis y letras. Esto nos da reglas como $E \to EC_+T$ en vez de $E \to E+T$. Las reglas que ya son un solo terminal (como $E \to a$) se dejan como estan.

Segundo, las reglas con 3 simbolos en el lado derecho se parten en dos usando un no terminal auxiliar. Por ejemplo, $E \to EC_+T$ se convierte en $E \to ED_1$ y $D_1 \to C_+T$. Aplicamos lo mismo a $TC_*F$ (auxiliar $D_2$) y $C_{(}EC_{)}$ (auxiliar $D_3$). El resultado final tiene solo reglas de dos no terminales o un terminal, que es exactamente CNF.

Paso 1. No hay producciones $\varepsilon$ ni unitarias. $\checkmark$

Paso 2. No terminales para terminales en producciones con $|\alpha| \geq 2$:

$C_a \to a,\quad C_b \to b,\quad C_0 \to 0,\quad C_1 \to 1,\quad C_+ \to +,\quad C_* \to *,\quad C_{(} \to (,\quad C_{)} \to )$

Paso 3. Reemplazo de terminales en producciones largas:

$$\begin{aligned} E &\to EC_+T \mid TC_*F \mid C_{(}EC_{)} \mid a \mid b \mid IC_a \mid IC_b \mid IC_0 \mid IC_1 \\ T &\to TC_*F \mid C_{(}EC_{)} \mid a \mid b \mid IC_a \mid IC_b \mid IC_0 \mid IC_1 \\ F &\to C_{(}EC_{)} \mid a \mid b \mid IC_a \mid IC_b \mid IC_0 \mid IC_1 \\ I &\to a \mid b \mid IC_a \mid IC_b \mid IC_0 \mid IC_1 \end{aligned}$$

Paso 4. Binarizacion ($D_1 \to C_+T$, $D_2 \to C_*F$, $D_3 \to EC_{)}$):

$$\begin{aligned} E &\to ED_1 \mid TD_2 \mid C_{(}D_3 \mid a \mid b \mid IC_a \mid IC_b \mid IC_0 \mid IC_1 \\ T &\to TD_2 \mid C_{(}D_3 \mid a \mid b \mid IC_a \mid IC_b \mid IC_0 \mid IC_1 \\ F &\to C_{(}D_3 \mid a \mid b \mid IC_a \mid IC_b \mid IC_0 \mid IC_1 \\ I &\to a \mid b \mid IC_a \mid IC_b \mid IC_0 \mid IC_1 \\[4pt] D_1 &\to C_+T \quad D_2 \to C_*F \quad D_3 \to EC_{)} \\[4pt] C_a &\to a \quad C_b \to b \quad C_0 \to 0 \quad C_1 \to 1 \\ C_+ &\to + \quad C_* \to * \quad C_{(} \to ( \quad C_{)} \to ) \quad \blacksquare \end{aligned}$$

Gramatica

Solucion

Gramatica original

$$\begin{aligned} E &\to E + T \mid T * F \mid (E) \mid a \mid b \mid Ia \mid Ib \mid I0 \mid I1 \\ T &\to T * F \mid (E) \mid a \mid b \mid Ia \mid Ib \mid I0 \mid I1 \\ F &\to (E) \mid a \mid b \mid Ia \mid Ib \mid I0 \mid I1 \\ I &\to a \mid b \mid Ia \mid Ib \mid I0 \mid I1 \end{aligned}$$

Paso 1: Verificar que no hay producciones epsilon ni producciones unitarias

La gramatica no tiene producciones $\varepsilon$ ni producciones unitarias (de la forma $A \to B$). Todas las producciones ya generan al menos un terminal o tienen al menos dos simbolos en el lado derecho.

Nota: Las producciones como $E \to a$ ya estan en forma CNF (un terminal). Las producciones como $I \to a$ tambien.

Paso 2: Introducir no terminales para terminales

En las producciones con longitud $\geq 2$ en el lado derecho, cada terminal debe ser reemplazado por un nuevo no terminal. Introducimos:

$$\begin{aligned} C_a &\to a \\ C_b &\to b \\ C_0 &\to 0 \\ C_1 &\to 1 \\ C_+ &\to + \\ C_* &\to * \\ C_{(} &\to ( \\ C_{)} &\to ) \end{aligned}$$

Paso 3: Reemplazar terminales en producciones largas

Las producciones con terminales mezclados con no terminales se reescriben:

$$\begin{aligned} E &\to EC_+T \mid TC_*F \mid C_{(}EC_{)} \mid a \mid b \mid IC_a \mid IC_b \mid IC_0 \mid IC_1 \\ T &\to TC_*F \mid C_{(}EC_{)} \mid a \mid b \mid IC_a \mid IC_b \mid IC_0 \mid IC_1 \\ F &\to C_{(}EC_{)} \mid a \mid b \mid IC_a \mid IC_b \mid IC_0 \mid IC_1 \\ I &\to a \mid b \mid IC_a \mid IC_b \mid IC_0 \mid IC_1 \end{aligned}$$

Paso 4: Binarizar producciones con mas de 2 simbolos

Las producciones con 3 simbolos en el lado derecho deben descomponerse en pares. Introducimos no terminales auxiliares:

Para $EC_+T$ (longitud 3):

$E \to ED_1 \quad \text{donde} \quad D_1 \to C_+T$

Para $TC_*F$ (longitud 3):

$E \to TD_2, \quad T \to TD_2 \quad \text{donde} \quad D_2 \to C_*F$

Para $C_{(}EC_{)}$ (longitud 3):

$E \to C_{(}D_3, \quad T \to C_{(}D_3, \quad F \to C_{(}D_3 \quad \text{donde} \quad D_3 \to EC_{)}$

Conversion paso a paso

Navega cada etapa de la conversion interactivamente:

Resultado: Gramatica en CNF

$$\begin{aligned} E &\to ED_1 \mid TD_2 \mid C_{(}D_3 \mid a \mid b \mid IC_a \mid IC_b \mid IC_0 \mid IC_1 \\ T &\to TD_2 \mid C_{(}D_3 \mid a \mid b \mid IC_a \mid IC_b \mid IC_0 \mid IC_1 \\ F &\to C_{(}D_3 \mid a \mid b \mid IC_a \mid IC_b \mid IC_0 \mid IC_1 \\ I &\to a \mid b \mid IC_a \mid IC_b \mid IC_0 \mid IC_1 \\[6pt] D_1 &\to C_+T \\ D_2 &\to C_*F \\ D_3 &\to EC_{)} \\[6pt] C_a &\to a \\ C_b &\to b \\ C_0 &\to 0 \\ C_1 &\to 1 \\ C_+ &\to + \\ C_* &\to * \\ C_{(} &\to ( \\ C_{)} &\to ) \end{aligned}$$

Verificacion del formato CNF

Todas las producciones tienen una de las dos formas validas:

• $A \to BC$ (dos no terminales): $ED_1$, $TD_2$, $C_{(}D_3$, $IC_a$, $IC_b$, $IC_0$, $IC_1$, $D_1 \to C_+T$, $D_2 \to C_*F$, $D_3 \to EC_{)}$
• $A \to a$ (un terminal): $E \to a$, $E \to b$, $T \to a$, $T \to b$, $F \to a$, $F \to b$, $I \to a$, $I \to b$, y todas las $C_x \to x$

$\checkmark$ La gramatica esta en forma normal de Chomsky.

Nota

La gramatica original representa expresiones aritmeticas con identificadores. Los identificadores ($I$) son secuencias de letras ($a$, $b$) y digitos ($0$, $1$) que empiezan con una letra. La conversion a CNF preserva el lenguaje generado.