La Jerarquía de Chomsky

Rubén Rodríguez Abril

La Jerarquía de Chomsky clasifica, de menor a mayor complejidad, a las diferentes gramáticas (conjunto de reglas) a partir de las cuales es posible generar expresiones de un lenguaje formal. Las estructuras lingüísticas generadas por cada una de estas gramáticas son solamente reconocibles por un determinado tipo de autómata.

Origen de la Jerarquía de Chomsky

¿Qué tipos de lenguajes escritos pueden ser comprendidos por un autómata? ¿qué tipo de estructuras lingüísticas son susceptibles de ser “traducidas” a estados internos de una máquina (y viceversa)? ¿hay estructuras gramaticales que son reconocidas por unos tipos de autómatas, pero no por otros?

Para responder a estas cuestiones y sistematizar todo el conocimiento sobre la materia existente hasta la fecha, el lingüista estadounidense Noam Chomsky, publicó en el año 1956 un artículo titulado “Tres modelos para la descripción del lenguaje” (“Three models for the description of language”). En su trabajo Chomsky elaboró una clasificación de gramáticas conocida a día de hoy como la Jerarquía de Chomsky. 

Retrato de Noam Chomsky

Estas gramáticas formales, interpretables por dispositivos automáticos, fueron agrupadas en tres (con posterioridad, en cuatro) categorías diferentes. Por increíble que parezca, existe una correspondencia uno a uno entre las diferentes clases de gramáticas formales y algunos tipos de autómatas, lo que sugiere una conexión intrínseca entre las Ciencias de la Computación y la Lingüística.

Lenguajes formales

Un lenguaje formal (L) es el conjunto de cadenas de caracteres que pueden ser formados a partir de letras tomadas de un alfabeto Σ, obedeciendo unas reglas de construcción determinadas denominadas gramática formal. El número de cadenas que pueden formarse a partir de un cierto alfabeto es, en principio, infinito. Y el conjunto de todas ellas se denomina clausura de Kleene Σ*. La labor del autómata es determinar cuáles de estas cadenas están bien formadas con arreglo a las reglas de la gramática formal en cuestión. Cuando el autómata es capaz de realizar esta tarea, se dice que acepta el lenguaje L. Las reglas para la formación de nuevas cadenas (“palabras”) reciben el nombre de reglas de producción (P). Los lenguajes formales reciben este nombre en contraposición a los lenguajes naturales, que son aquellos directamente interpretables por el cerebro humano (como el español o el francés).

Lenguaje Formal con Alfabeto y Reglas de Producción

Un ejemplo sencillo de un lenguaje formal. Consta de un alfabeto de cinco símbolos y una gramática con tres reglas de generación. A la derecha se muestra como la combinación de reglas con símbolos da lugar a las diferentes expresiones del lenguaje. A estas expresiones podemos también llamarlas cadenas o palabras y es evidente que el número de ellas es potencialmente infinito.

Como ya hemos señalado, la Jerarquía de Chomsky clasifica los lenguajes formales en cuatro categorías diferentes:

Jerarquía de Chomsky y los lenguajes regulares

El rimero de los lenguajes formales de la Jerarquía de Chomsky son los lenguaje regulares. Estos son generados por gramáticas regulares (tipo 3) y aceptados por autómatas de estado finito.

Las reglas de producción a aplicar son las siguientes (en este caso es una gramática regular por la izquierda)

I        A ⇒ B

II      A ⇒ Ba

III    A ⇒ ε

IV    A ⇒ a

donde las variables en mayúscula (A, B, y S, el símbolo inicial) son símbolos no terminales (sobre los que se puede continuar aplicando reglas de producción), mientras que las variables en minúscula (a, b) son símbolos terminales, es decir, definitivos. El símbolo ε denota un conjunto vacío. Solo las cadenas que carezcan de símbolos no terminales se consideran expresiones del lenguaje.

Cuando existen reglas del tipo IV se dice que estamos ante una gramática regular ampliada.

Gramáticas Regulares. Lenguaje Tipo 3 de la Jerarquía de Chomsky.

Un ejemplo sencillo de lenguaje regular. A la izquierda algunas reglas propias de una gramática regular. A la derecha mostramos una posible ruta de producción de una palabra del lenguaje. Las celdas en azul denotan los símbolos no terminales sobre los que cabe aplicar una nueva regla de producción.

Ejemplo: conjugación de verbos

La conjugación de un verbo regular puede realizarse aplicando las reglas de una gramática regular por la izquierda, en donde los símbolos terminales corresponderían a la palabra en formación mientras que los símbolos terminales equivaldrían a los diferentes morfemas del verbo (tronco y desinencias).

Esquema de la formación de un verbo haciendo uso de reglas de producción.

En esta imagen se describe la producción de una forma verbal regular. Se trata de la primera persona del singular del verbo cantar. Los símbolos en azul son no terminales, y representan a la palabra en formación. Los símbolos en blanco y negro son terminales, y representan a los morfemas del verbo. En este caso, a señala la desinencia correspondiente a la persona gramatical («mos»), b la del tiempo verbal («ría»), y por último c, el tronco del verbo («canta»).

El esquema señalado puede ser utilizado para construir cualquier otra estructura gramatical de un lenguaje natural que sea regular, como por ejemplo, la flexión nominal.

Lenguajes libres de contexto

Los lenguaje libres de contexto son generados por gramáticas libres de contexto (tipo 2) y aceptados por autómatas con pila no deterministas. Permiten la formación de estructuras recursivas como las oraciones subordinadas en los lenguajes naturales, las cláusulas entre paréntesis en las fórmulas aritméticas, o las subrutinas/funciones en los lenguajes de programación. Se les aplica la siguiente regla de producción:

V        A ⇒ α

donde A es un símbolo no terminal, mientras que α es una cadena de símbolos terminales y no terminales con la posibilidad de ser también un conjunto vacío.

Como el lector puede comprobar, las reglas I a IV (gramáticas regulares) pueden ser entendidas como subtipos de la regla V. Por tanto, toda gramática regular es siempre una gramática libre de contexto.

Gramáticas Libres de Contexto. Lenguaje Tipo 2 de la Jerarquía de Chomsky.

Ejemplo: fórmulas aritméticas

A modo de ejemplo, construiremos una gramática libre de contexto que permita la creación de fórmulas algebraicas simples. Esta gramática estará dotada de las reglas de producción siguientes:

1)   S ⇒ A = B

2)   C ⇒ α * β

3)   D ⇒ (α * β)

4)   E ⇒ c

donde S es el símbolo inicial; A, B, C, DE son símbolos no terminales (expresiones de la fórmula), α y β pueden ser terminales (constantes) o no terminales (expresiones), c es terminal (constante) y por último * puede ser cualquiera de los cuatro operadores algebraicos fundamentales (+, , ×, ÷), que son operadores terminales La primera y la segunda reglas se aplican respectivamente en el primer y segundo paso en la creación de la fórmula. Y la tercera regla en todos los pasos ulteriores.
Producción de una fórmula aritmética aplicando reglas de producción libres de contexto.

En la imagen se muestra la producción de una fórmula aritmética elemental, aplicando sucesivamente reglas de transformación de tipo V. Las expresiones en formación, que son símbolos no terminales, aparecen dibujadas en azul. Los símbolos terminales, que pueden ser constantes u operadores, se dibujan en blanco y negro. Es la existencia de símbolos azules transformables mediante una regla tipo V lo que permite construir expresiones cuyos operandos pueden consistir a su vez en otras expresiones, lo cual permite la posibilidad de recursión.

Cuando una fórmula aritmética ha sido construida con arreglo a los procedimientos antedichos se dice que es una fórmula bien formada.

Lenguajes sensibles al contexto

Los lenguajes sensibles al contexto son generados por gramáticas sensibles al contexto (tipo 1) y aceptados por máquinas de Turing linealmente acotadas (aquellas cuya cinta es finita).

Como su propio nombre indica, en estos lenguajes, el resultado la manipulación de cada símbolo depende de la configuración de los símbolos vecinos. Estas gramáticas son capaces de capturar fenómenos lingüísticos relacionados con el contexto como la concordancia gramatical y, en el ámbito de la compilación, distinguir entre variables globales o locales (que sólo tienen validez en un bloque de código, pero no en el resto del programa). Sus reglas de producción tienen que adecuarse a la ecuación siguiente

VI        αAβ ⇒ αλβ

donde A es un símbolo no terminal, α y β cadenas de símbolos terminales o no terminales que pueden estar vacías y λ una cadena de símbolos terminales o no terminales que nunca puede estar vacía. Como el lector puede comprobar, la transformación del símbolo A puede depender del contenido de sus símbolos adyacentes. Si así sucede, estamos ante un lenguaje dependiente del contexto, en caso contrario, estamos ante un lenguaje de tipo 2 (independiente del contexto), construido con arreglo a reglas de la clase V.

Gramáticas Sensibles al Contexto. Lenguaje Tipo 1 de la Jerarquía de Chomsky.

Ejemplo: concordancia nominal

Esto puede utilizarse para crear reglas de producción que garanticen la concordancia gramatical en un lenguaje natural. A modo de ejemplo, crearemos un lenguaje formal cuya misión es garantizar la concordancia entre nombre, artículo y adjetivo. Sus reglas de producción estarán dotados de la estructura siguiente:

aNb ⇒ anb

donde a es un artículo, b un adjetivo, N el sustantivo sin declinar, y n el sustantivo declinado. Los tres símbolos están separados por un espacio. El objetivo del autómata (linealmente acotado en este caso) es devolver la forma gramaticalmente correcta del sustantivo.

Potencia de los sistemas de NLP

Marvin Minsky señalaba que, en su opinión, los sistemas informáticos actuales se aproximaban bastante al modelo del autómata linealmente acotado. Esta apreciación es importante, porque equivale a señalar que, en principio, los actuales sistemas de procesado natural de lenguaje, si están diseñados adecuadamente, son capaces de reconocer gramáticas de los tipos 1, 2 y 3, y por lo tanto de capturar fenómenos lingüísticos tan importantes como el contexto o la recursión. Tal vez eso explique la extraordinaria eficiencia de los modernos métodos de traducción a máquina basados en el Deep Learning.

Lenguajes recursivamente enumerables

El último de los lenguajes en la Jerarquía de Chomsky son los lenguajes recursivamente enumerables, aquellos que puede ser construidos por una gramática formal cualquiera (gramáticas tipo 0). Es el conjunto de lenguajes que pueden ser reconocidos y aceptados por (al menos) un autómata. Dado que las máquinas de Turing son los autómatas de mayor poder computacional, alternativamente pueden definirse a estos lenguajes como aquellos que pueden ser aceptados por una máquina de Turing.

Lenguajes Recursivos

Todos los lenguajes que hemos expuesto en párrafos anteriores son recursivos, esto es, es posible construir una máquina de Turing total o decisor (una máquina cuya parada está garantizada) que acepte el lenguaje. Cada vez que queramos verificar la validez formal de una cadena de texto (por ejemplo si una fórmula está bien formada o un verbo está bien conjugado), dicha cadena deberá ser presentada a la máquina de Turing. Si pertenece al lenguaje, la máquina se parará y devolverá el valor booleano verdadero. Si no pertenece al lenguaje, la máquina se parará devolviendo el valor falso. En ningún caso el autómata puede quedarse colgado, funcionando indefinidamente sin detenerse. Por este motivo, dentro de un lenguaje recursivo siempre es posible construir un algoritmo/autómata que resuelva el Problema de Decisión (Entscheidungsproblem) de David Hilbert. Y dicho algoritmo/autómata será matemáticamente equivalente a una función recursiva.

Lenguajes no Recursivos

Existen, sin embargo, determinados tipos de lenguajes no recursivos en los que es posible construir cadenas de texto cuya validez o invalidez formales no puede ser demostrada, y que quedan arrojados al ámbito etéreo de la indemostrabilidad. Se trata de aquellos cuya verificación corresponde a una máquina de Turing cuya parada no está garantizada. En este caso, si la cadena presentada pertenece al lenguaje, la máquina se para y devuelve el valor booleano verdadero. Si no pertenece al lenguaje, la máquina puede pararse devolviendo el valor falso o bien puede seguir funcionando indefinidamente. En este último supuesto el autómata no nos ofrecerá ninguna respuesta definitiva y la validez formal de la cadena devendrá una cuestión indecidible. Dado que la parada de la máquina sí que está garantizada en el caso de la validez de una cadena, se dice que los lenguajes recursivamente demostrables son semidecidibles.

Gramáticas formales y sistemas lógicos

Las gramáticas formales pueden utilizarse para modelar cualquier sistema lógico-axiomático en el que los teoremas se demuestren recursivamente, utilizando métodos de manipulación de símbolos, a partir de los axiomas del sistema, como sucede en la Aritmética de Peano. En este caso, el lenguaje viene constituido por todos los teoremas que puedan construirse dentro de dicha aritmética. Las reglas de producción son las reglas de manipulación simbólica por medio de las cuales se generan nuevos teoremas a partir de los ya existentes. Y la labor de la máquina de Turing característica es la de señalar si la cadena/teorema (por ejemplo la conjetura de Goldbach o el último teorema de Fermat) que se le presenta pertenece o no al lenguaje de que se trate.

Procesos irreversibles

Todas las reglas de producción de las gramáticas formales siguen el esquema siguiente:

VII        α ⇒ γ

donde α y γ son cadenas con símbolos terminales y no terminales. α nunca puede estar vacía (es decir, no es posible crear cadenas de símbolos de la nada).

Dependiendo del tipo de gramática puede ser permisible que γ esté vacía. Cuando ello sucede, se dice que estamos ante una gramática irrestricta. En tal caso es posible la eliminación de símbolos terminales, lo cual conlleva pérdida de información e introduce irreversibilidad en el proceso de formación de nuevos teoremas.

En las otras gramáticas las reglas de producción son reversibles, y el autómata puede, para comprobar la validez de una palabra, revertir la aplicación de las mismas. Si se alcanza el estado inicial S, la palabra pertenece al lenguaje.

Por el contrario, en el caso de las gramáticas irrestrictas, la eliminación completa de cadenas de caracteres en una fórmula, impide que la máquina de Turing pueda revertir el proceso de derivación del teorema a partir de los axiomas.

Gramáticas Recursivamente Universales. Lenguaje Tipo 0 de la Jerarquía de Chomsky.

En este ejemplo, la aplicación de la regla 3 supone un paso irreversibles en el proceso de producción de expresiones. No hay forma de que una Máquina de Turing vuelva al punto de partida.

Esquema de un proceso deductivo algebraico irreversible.

La máquina de Turing no es capaz de retroceder en este proceso deductivo. No puede determinar con certeza de cuál de las tres fórmulas de la segunda fila ha sido deducida 2x.

Aritmética y gramática irrestricta

La Aritmética de Peano posee elementos neutros, tanto en suma (expresiones equivalentes a 0) como en la multiplicación (expresiones equivalentes a 1), que pueden ser eliminados durante el correspondiente paso del proceso deductivo. Como consecuencia de ello, la gramática que la representa debe ser considerada irrestricta, y el conjunto de teoremas que pueden ser deducidos de sus axiomas conforma un lenguaje no recursivo.

Jerarquía de Chomsky

La clasificación que acabamos de describir es de naturaleza jerárquica, de tal modo que las gramáticas situadas en los niveles más bajos son englobadas en las de los niveles más altos, constituyendo una suerte de estructura de “muñecas rusas”. Así, las gramáticas tipo 3 forman parte también de las gramáticas tipo 2, y éstas a su vez, de las de tipo 1 y 0.

La Jerarquía de Chomsky tiene su plena correspondencia en el ámbito de la jerarquía de autómatas: así, las máquinas de Turing pueden simular el comportamiento de un autómata de pila (aunque lo contrario no es cierto), y éste a su vez puede realizar las tareas que puede realizar una autómata de estado finito.

Jerarquía de Chomsky anidada

La Jerarquía de Chomsky es extraordinariamente importante en el ámbito del procesamiento del lenguaje natural, toda vez que nos señala qué tipo de estructuras lingüísticas puede reconocer un tipo determinado de autómatas. Por ese motivo haremos más de una vez referencia a esta clasificación en los artículos subsiguientes de esta serie.

Lecturas Recomendadas

– Chomsky, N. (1956) Three models for the description of language.