Esta entrada pertenece a la serie Teoría de la computación, ¡platicada!
Como se vio en la entrega pasada, no todos los lenguajes pueden ser expresados (o mejor dicho: producidos) con un autómata finito. Algunos lenguajes son conjuntos de cadenas que no pueden ser descritos de esa manera. Una ampliación a las capacidades de los autómatas finitos y expresiones regulares se encuentra en los lenguajes libres de contexto.
Reglas de producción
Una gramática de este tipo consiste en un conjunto de reglas de sustitución, también conocidas como reglas de producción. Cada regla consiste en dos partes: una variable (la que se sustituye), y una cadena resultado, formada por otras variables y/o símbolos terminales. Una regla podría ser algo como esto:
\(\displaystyle A \rightarrow Ba\)
En este ejemplo existe una regla que especifica, en el lado izquierdo, la variable \(A\) que se verá sustituida por una cadena que consiste en otra variable llamada \(B\), y un terminal representado con el símbolo \(a\) (es usual que las variables se representen con letras mayúsculas, y el resto de símbolos con minúsculas).
Un lenguaje, como el especificado en la entrega pasada, consistente en todas las cadenas que inician con \(n\) símbolos \(a\) y terminan con el mismo número de símbolos \(b\), se podría escribir como:
\(\displaystyle
S \rightarrow aSb\\
S \rightarrow \varepsilon\)
Esto mismo de puede escribir de forma más compacta como:
\(\displaystyle S \rightarrow aSb \, | \, \varepsilon\)
Donde \(\varepsilon\) representa una cadena vacía. La forma de producir una cadena del lenguaje es, simplemente, haciendo sustituciones sucesivas de las variables por alguna de las cadenas que establecen las reglas de producción. Así, en este ejemplo, para producir la cadena \(aaabbb\) se procedería como sigue:
| Variable inicial | \(S\) |
| Se sustituye \(S\) por \(aSb\) | \(aSb\) |
| Se sustituye \(S\) por \(aSb\) | \(aaSbb\) |
| Se sustituye \(S\) por \(aSb\) | \(aaaSbbb\) |
| Se sustituye \(S\) por \(\varepsilon\), que es la cadena vacía. | \(aaabbb\) |
Dicho de una manera un poco más formal, una gramática libre de contexto está formado por una tupla de cuatro elementos que son:
- Un conjunto finito \(V\) de variables.
- Un conjunto finito \(\Sigma\) de símbolos terminales.
- Un conjutno finito \(R\) de reglas, que indican las sustituciones posibles de cada variable.
- Una variable \(S \in V\) que es la inicial, aquella que inicia las sustituciones.
Es decir, que un lenguaje libre de contexto \(L\) se puede expresar como:
\(\displaystyle L = \{ V, \Sigma, R, S\}\)
Forma normal de Chomsky
Para un mismo lenguaje regular, existen muchos conjuntos de reglas de producción que lo generan, pero existe al menos uno que siempre cumple que, o bien todas sus reglas de producción poseen un símbolo terminal, o bien, dos no terminales. Es decir, todas sus reglas de producción son de alguna de estas dos formas:
\(\displaystyle A \rightarrow BC \\A \rightarrow \alpha\)
Donde \(A\) y \(B\) son símbolos no terminales y \(\alpha\) es un símbolo terminal. A esta forma se le conoce como forma normal de Chomsky, y es bastante útil ya que convierte al árbol de producción en un árbol binario, que es fácilmente manejable por medios algorítmicos.
¿Y por qué se llama forma normal de Chomsky? Bueno, porque Noam Chomsky probó que una forma así existe para todo lenguaje libre de contexto.
Un regular es libre de contexto
Tal y como dice el título de esta sección, un lenguaje regular es también un lenguaje libre de contexto. En otras palabras: todo lenguaje regular se puede generar con reglas de producción como las mencionadas aquí. El caso contrario no es verdad. Es decir, que no todo lenguaje libre de contexto es regular, y por tanto, no todo lenguaje libre de contexto se puede producir utilizando un autómata regular o describir con una expresión regular.
En la siguiente entrega bordaremos la ambigüedad en los lenguajes libres de contexto.
