Siguiente: Forma normal de Greibach Un nivel arriba: Formas normales Anterior: Formas normales

Forma normal de Chomsky

Una gramática libre de contexto G=(V,T,P,S) se dice estar en forma normal de Chomsky si sus producciones son de cualquiera de las dos formas

• $X\rightarrow YZ$ con $X,Y,Z\in V$, o bien
• $X\rightarrow a$ con $X\in V$ y $a\in T$.

Proposición 3.1   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 Chomsky.

En efecto, dada una gramática G, apliquemos el último procedimiento de la sección anterior para transformar a G en una gramática G'' sin variables inútiles ni producciones vacías ni producciones unitarias equivalente a G. A las producciones que quedasen de la forma $X\rightarrow a$ con $X\in V$ y $a\in T$ las dejamos sin cambio alguno. A cada producción de la forma $X\rightarrow \xi_1\xi_2\cdots\xi_k$, con $\xi_1\xi_2\cdots\xi_k\in (V+T)^*$ y $k\geq 2$, la transformamos en una sucesión de producciones de la forma siguiente: A cada símbolo terminal $a\in T$ que aparezca en la palabra $\xi_1\xi_2\cdots\xi_k$ le asociamos una variable nueva X_a e incorporamos la producción $X_a\rightarrow a$. Así pues las producciones que no sean de la forma $X\rightarrow a$ con X variable y a terminal, han de ser de la forma $X\rightarrow X_1X_2\cdots X_k$, con $X, X_1X_2\cdots X_k$ todos variables. Para cada una de estas últimas producciones introducimos k-2 nuevas variables $Y_1,\ldots Y_{k-2}$ e incorporamos la sucesión de producciones

$$\begin{array}{lcl} X &\rightarrow& X_1Y_1 \\ Y_1 &\rightar... ...2}Y_{k-2} \\ Y_{k-2} &\rightarrow& X_{k-1}X_{k} \end{array}$$

Obtenemos así la forma normal equivalente a la gramática dada.
Siguiente: Forma normal de Greibach Un nivel arriba: Formas normales Anterior: Formas normales