La jerarquía de Chomsky

La jerarquía de Chomsky organiza los lenguajes formales en cuatro clases anidadas, cada una definida por una restricción en las reglas gramaticales y emparejada con un tipo distinto de máquina abstracta.

Definition

La jerarquía de Chomsky es una clasificación de gramáticas formales mediante restricciones progresivamente más fuertes en sus reglas de producción, lo que produce las clases de lenguaje regular, libre de contexto, sensible al contexto y recursivamente enumerable en una cadena de inclusiones estrictas.

Scope

Este tema cubre los cuatro tipos de gramática —irrestricta, sensible al contexto, libre de contexto y regular—, su contención estricta y el modelo de autómata correspondiente a cada nivel, a saber, la máquina de Turing, el autómata linealmente acotado, el autómata de pila y el autómata finito, junto con las propiedades de cierre y decidibilidad que separan los niveles.

Core questions

• ¿Cómo se traducen las restricciones en las reglas gramaticales en límites de memoria y poder computacional?
• ¿Por qué cada nivel de la jerarquía está estrictamente contenido en el siguiente?
• ¿Qué modelo de autómata corresponde a cada tipo de gramática?
• ¿Cómo cambian las propiedades de decidibilidad y cierre a medida que se asciende en la jerarquía?

Key theories

Correspondencia gramática-máquina

Cada clase de gramática es reconocida por un modelo de máquina específico —regular por autómatas finitos, libre de contexto por autómatas de pila, sensible al contexto por autómatas linealmente acotados e irrestricta por máquinas de Turing—, lo que vincula las descripciones generativas y operacionales de la computación.

Inclusión estricta de las clases de lenguaje

Cada nivel contiene propiamente al que está debajo, evidenciado por lenguajes separadores concretos, por lo que la jerarquía es una verdadera escalera de poder expresivo creciente en lugar de una colección de descripciones equivalentes.

Clinical relevance

La jerarquía es el mapa organizador de la teoría del lenguaje formal: indica a los diseñadores de lenguajes de programación, lenguajes de consulta y especificaciones de protocolo cuánta maquinaria requiere una clase dada de patrones, y enmarca el límite entre lo que es decidible y lo que solo es reconocible.

History

Chomsky propuso la jerarquía a finales de la década de 1950 mientras buscaba modelos formales de la sintaxis del lenguaje natural, y las correspondencias con las máquinas se establecieron a medida que la teoría de autómatas maduró a lo largo de la década de 1960, con los autómatas linealmente acotados introducidos por Myhill y el nivel sensible al contexto aclarado por Kuroda.

Key figures

• Noam Chomsky
• Marcel-Paul Schützenberger
• John Myhill

Seminal works

• hopcroft2006
• sipser2013

Frequently asked questions

¿Cuáles son los cuatro niveles de la jerarquía de Chomsky?

De menor a mayor potencia son los lenguajes regulares (Tipo 3), los lenguajes libres de contexto (Tipo 2), los lenguajes sensibles al contexto (Tipo 1) y los lenguajes recursivamente enumerables (Tipo 0). Cada nivel relaja las restricciones en las reglas gramaticales y corresponde a una máquina con más memoria.

¿El lenguaje natural está capturado por la jerarquía de Chomsky?

La jerarquía fue motivada originalmente por la lingüística, pero la mayoría de los lingüistas concluyen que los lenguajes naturales no son libres de contexto, situándose en un nivel a menudo llamado ligeramente sensible al contexto. La jerarquía sigue siendo fundamental en la informática, aunque el lenguaje humano se ajusta a ella solo de forma aproximada.