Lenguajes libres de contexto

Lo que ya visto:

$$\begin{eqnarray*} L_{ab}&=&\{a^nb^n\;\vert\;n\geq 0\} \\ L_{abc}&=&\{a^nb^nc^n\... ... \\ L_{()}&=&\{w\;\vert\;w\in\{(,)\}^*,w \mbox{ correcto}\} \\ \end{eqnarray*}$$

Una gramática libre de contexto es una cuádrupla

$$G=(\Sigma_N,\Sigma_T,P,\$)$$

donde

• $\Sigma_N$ es un alfabeto de símbolos no-terminales (o variables)
• $\Sigma_T$ es un alfabeto de símbolos terminales (o constantes)
• $P\subset\Sigma_N\times(\Sigma_N\cup\Sigma_T)^+\cup\{\$\longrightarrow \epsilon\}$ es un sistema de producciones (o reglas)
• $\$\in\Sigma_N$ es el símbolo inicial

Es decir, la definición de las gramáticas libres de contexto nos da mucha libertad para el sistema de producciones.

Por eso (y también para otros objetivos como por ejemplo mostrar que existe un tipo de autómata que justamente acepta lenguajes libres de contexto como veremos en adelante) se ha desarrollado formas normales de la representación de gramáticas libres de contexto, es decir, se transforma el sistema de producciones de la gramática de tal manera que no se varía el lenguaje generado pero las reglas tengan cierta propiedad.

Especialmente la definición arriba exluye reglas de forma $X\longrightarrow \epsilon$ siendo $X$ un símbolo no-terminal diferente a $\$, sin embargo, si permitesemos tales producciones, es decir, permitir $P\subset\Sigma_N\times(\Sigma_N\cup\Sigma_T)^*$, obtendríamos los mismos lenguajes, porque, como veremos a continuación, dichas producciones se pueden eliminar sin cambiar el lenguaje que genera la gramática.