Alfabetos, lenguajes y gramáticas

La teoría de la computación arranca con una decisión de modelado que parece una simplificación excesiva: todo problema se reduce a decidir si una cadena de símbolos pertenece a un conjunto. Esa reducción es lo que después permite demostrar que ciertos problemas no se pueden resolver.

Alfabeto, cadena y lenguaje

Un alfabeto es un conjunto finito de símbolos, $\Sigma$. Una cadena es una secuencia finita de símbolos del alfabeto, incluida la cadena vacía $\varepsilon$. Un lenguaje es un conjunto de cadenas, es decir, cualquier subconjunto de $\Sigma^*$.

La palabra “lenguaje” despista: no hay semántica ni significado. Los números primos escritos en binario son un lenguaje. Los programas Java que compilan son un lenguaje. Las cadenas con la misma cantidad de paréntesis abiertos y cerrados, también.

Todo problema de decisión es un lenguaje

Con eso, un problema de decisión es un lenguaje, y resolverlo es decidir la pertenencia: dada una cadena, responder si está o no. Toda la teoría se construye sobre esa equivalencia.

Hay un argumento de conteo que conviene ver temprano. Los lenguajes sobre un alfabeto son incontables —hay tantos como subconjuntos de un conjunto infinito numerable— mientras que los programas son contables, porque cada uno es una cadena finita. Por lo tanto hay lenguajes sin programa, y muchísimos más de los que sí lo tienen. Que exista lo incomputable se sabe antes de encontrar un solo ejemplo.

Describir infinitas cadenas con reglas finitas

Un lenguaje infinito necesita una descripción finita, y una gramática es una de ellas: un conjunto de reglas que reescriben símbolos. Se parte de un símbolo inicial y se aplican reglas hasta quedarse sin símbolos que reescribir.

Las reglas tienen la forma $A \to \alpha$: reemplazar la izquierda por la derecha. El lenguaje generado es el conjunto de todas las cadenas de símbolos terminales que se pueden derivar. La misma cadena puede derivarse de varias formas, y eso es exactamente la ambigüedad que un diseñador de lenguajes trata de evitar.

Los cuatro niveles de Chomsky

Restringir la forma de las reglas define la jerarquía de Chomsky, cuatro niveles encajados:

• Regulares: una sola variable a lo sumo, siempre del mismo lado. Los reconocen los autómatas finitos.
• Libres de contexto: la izquierda es una sola variable. Autómatas de pila.
• Sensibles al contexto: las reglas no acortan la cadena. Autómatas linealmente acotados.
• Recursivamente enumerables: sin restricciones. Máquinas de Turing.

Cada nivel es estrictamente más expresivo que el anterior, y cada uno tiene su máquina.

Los ejemplos que separan un nivel del otro

Los ejemplos que separan los niveles son sencillos de recordar. Las cadenas con una cantidad par de ceros son regulares: alcanza con recordar un bit.

Las cadenas $a^n b^n$ no lo son: hay que contar, y contar sin límite necesita memoria ilimitada. Son libres de contexto, y el autómata de pila las reconoce apilando y desapilando. Las cadenas $a^n b^n c^n$ ya no: una pila sola no alcanza para dos correspondencias. Ahí hace falta el nivel siguiente.

Dónde aparece esto sin que nadie lo nombre

Esto se usa todos los días sin nombrarlo. Un compilador tiene dos etapas por este motivo: el analizador léxico reconoce tokens con expresiones regulares, y el sintáctico arma el árbol con una gramática libre de contexto.

El malentendido más común de la industria sale de acá: HTML anidado no es regular, así que una expresión regular no puede parsearlo. No es una limitación de la biblioteca, es de la clase de lenguaje.

Por qué todo problema es un lenguaje

Cierre

Alfabeto, cadena, lenguaje: con eso un problema pasa a ser un conjunto y resolverlo, decidir pertenencia. Las gramáticas los describen en forma finita, y restringir sus reglas arma la jerarquía de Chomsky, donde cada clase de lenguaje tiene la máquina que le corresponde.