La Jerarquía de Chomsky

Rubén Rodríguez Abril

La Jerarquía de Chomsky explora, de menor a mayor complejidad, las diferentes reglas a partir de las cuales es posible generar expresiones de un lenguaje. Cada una de estas reglas gramaticales dotan a estas expresiones de una determinada estructura que son solamente reconocibles por un tipo de autómata.

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. 

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 Σ, y que obedecen unas reglas gramaticales determinadas, una 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, a las que dedicaremos este artículo.

Lenguajes regulares

Los lenguajes regulares 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 ⇒ a

II      A ⇒ B

III    A ⇒ Ba

IV    A ⇒ ε

donde las variables en mayúscula (A, B) 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.

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 terminales sobre los que cabe aplicar una nueva regla de producción.

Ejemplo: conjugación de verbos

Por medio de estas reglas pueden, por ejemplo, conjugarse verbos regulares del modo siguiente:

Desinencias verbales y Gramática Regular

Mediante las señaladas reglas de producción (concretamente, la primera y la tercera) puede construirse cualquier forma gramatical de un lenguaje natural que sea regular (conjugaciones verbales, desinencias del sustantivo). La primera regla se usaría para agregar morfemas y desinencias. La segunda, para agregar el tronco verbal o el del sustantivo.

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.

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 ⇒ (α * β)

donde S es el símbolo inicial; A, B, C y D son símbolos no terminales, α y β pueden ser terminales o no terminales, y por último * puede ser cualquiera de los cuatro operadores algebraicos fundamentales (+, , ×, ÷). 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.

Fórmulas Aritméticas y Gramática Libre de Contexto

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 depende del contenido de sus símbolos adyacentes.

Tipo 1 de la Jerarquía de Chomsky

Ejemplo: concordancia verbal

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 con la siguiente regla de producción, y cuya misión es garantizar la concordancia entre pronombre y forma verbal:

pV ⇒ pvd

donde p es un pronombre, V el verbo en formación, v el tronco verbal y d los morfemas y desinencias. Los símbolos p y v están separados por un espacio.

Redes neuronales

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 bien diseñados, 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 explica la extraordinaria eficiencia de los modernos métodos de traducción a máquina basados en el Deep Learning.

Lenguajes recursivamente enumerables

Los lenguajes recursivamente enumerables son generados por gramáticas irrestrictas (tipo 0) y aceptados por máquinas de Turing, cuya cinta es infinita. Para verificar su pertenencia al lenguaje, la cadena de texto es presentada a la máquina de Turing. Si pertenece al lenguaje, la máquina se para y devuelve el valor booleano verdadero. Si no pertenece al lenguaje, la máquina se para devolviendo el valor falso o bien sigue funcionando indefinidamente.

Las gramáticas irrestrictas 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 el caso de 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. Y la labor de la máquina de Turing 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

En las gramáticas irrestrictas pueden establecerse todo tipo de reglas de producción, sin restricción alguna. De particular importancia es la regla siguiente, que está expresamente prohibida en las otras gramáticas, pero está aceptada en las gramáticas irrestrictas:

VII        α ⇒ γ

donde α y γ son cadenas con símbolos terminales y no terminales, pudiendo γ estar vacía. Esta regla permite la eliminación de cadenas de caracteres, la 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 de tipo 0, 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.

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.

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.

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.

Aprende a programar redes neuronales desde cero.

La Máquina Oráculo utiliza cookies para que usted tenga la mejor experiencia de usuario. Si continúa navegando está dando su consentimiento para la aceptación de las mencionadas cookies y la aceptación de nuestra política de cookies, pinche el enlace para mayor información.plugin cookies

ACEPTAR
Aviso de cookies