Teoría del Lenguaje Formal y Autómatas

La teoría de los lenguajes formales y las máquinas abstractas que los reconocen, proporcionando el vocabulario para describir la complejidad de un patrón lingüístico y los algoritmos que pueden procesarlo.

Definition

La teoría del lenguaje formal estudia conjuntos de cadenas definidos por gramáticas, y la teoría de autómatas estudia las máquinas abstractas que deciden la pertenencia a esos conjuntos.

Scope

Cubre la jerarquía de Chomsky (lenguajes regulares, libres de contexto, sensibles al contexto, recursivamente enumerables), las gramáticas correspondientes y los autómatas de reconocimiento — máquinas de estados finitos, autómatas de pila y máquinas de Turing. Aborda las propiedades de cierre y decidibilidad relevantes para el procesamiento del lenguaje y la cuestión de dónde se sitúa el lenguaje natural en la jerarquía. Los lemas de bombeo y las pruebas completas de complejidad se tratan como antecedentes más que como contenido principal.

Core questions

• ¿Qué autómata corresponde a cada nivel de la jerarquía de Chomsky?
• ¿Dónde se sitúa el lenguaje natural en la jerarquía y por qué se argumenta que excede la potencia libre de contexto?
• ¿Qué significa que una clase de lenguaje esté cerrada bajo una operación y por qué es importante para la ingeniería?

Key concepts

• lenguaje regular
• gramática libre de contexto
• gramática sensible al contexto
• autómata de estados finitos
• autómata de pila
• máquina de Turing
• propiedades de cierre
• sensibilidad leve al contexto

Key theories

Jerarquía de Chomsky

Cuatro clases anidadas de lenguajes formales, cada una generada por un tipo de gramática restringida y reconocida por un autómata correspondiente, que ordenan las construcciones lingüísticas según la potencia computacional requerida.

Correspondencia gramática-autómata

Cada clase de gramática es demostrablemente equivalente a una clase de máquina — las gramáticas regulares a autómatas finitos, las gramáticas libres de contexto a autómatas de pila — vinculando las descripciones generativas con los algoritmos de reconocimiento.

History

El artículo de Chomsky de 1956 introdujo la jerarquía como parte de un argumento de que los modelos de estados finitos eran inadecuados para el lenguaje natural. Las décadas siguientes formalizaron las correspondencias de autómatas, y los lingüistas computacionales demostraron más tarde que el lenguaje natural requiere, como máximo, una potencia 'ligeramente sensible al contexto', lo que motivó formalismos gramaticales más allá de los libres de contexto.

Debates

¿Es el lenguaje natural libre de contexto?

Las dependencias interlingüísticas en lenguajes como el suizo alemán se utilizaron para argumentar que el lenguaje natural excede la potencia libre de contexto, lo que llevó a la noción de sensibilidad leve al contexto como el nivel adecuado de expresividad.

Key figures

• Noam Chomsky
• John Hopcroft
• Jeffrey Ullman
• Stephen Kleene

Seminal works

• chomsky1956
• hopcroft2006

Frequently asked questions

¿Cuál es la diferencia entre un lenguaje regular y un lenguaje libre de contexto?

Los lenguajes regulares pueden ser reconocidos con memoria finita por un autómata de estados finitos; los lenguajes libres de contexto pueden requerir una pila (un autómata de pila) para rastrear estructuras anidadas, como paréntesis balanceados o cláusulas incrustadas.