Autómatas y Lenguajes Formales
La teoría de autómatas y lenguajes formales estudia máquinas idealizadas de potencia creciente y las clases de cadenas, o lenguajes, que cada una puede reconocer, proporcionando una descripción matemática precisa de lo que constituye un patrón y lo que se necesita para detectarlo.
Definition
Un lenguaje formal es un conjunto de cadenas finitas sobre un alfabeto fijo, y un autómata es un dispositivo de computación abstracto cuyas computaciones de aceptación definen dicho lenguaje; el área clasifica los lenguajes según el tipo más simple de autómata o gramática que los genera o reconoce.
Scope
Esta área abarca los autómatas finitos y los lenguajes regulares, los autómatas de pila y los lenguajes libres de contexto, la jerarquía de Chomsky que relaciona las gramáticas con los modelos de máquinas, las propiedades de cierre y decisión de las clases de lenguajes, y los autómatas que procesan palabras y árboles infinitos, junto con las caracterizaciones algebraicas y lógicas que los acompañan.
Sub-topics
Core questions
- ¿Qué lenguajes puede reconocer una máquina con memoria finita y cuáles no puede reconocer?
- ¿Cómo se corresponden las gramáticas y los modelos de máquinas a través de los niveles de la jerarquía de Chomsky?
- ¿Qué preguntas sobre una clase de lenguaje, como la vacuidad o la equivalencia, son algorítmicamente decidibles?
- ¿Cómo se extienden los autómatas a palabras y árboles infinitos, y por qué esto es importante para la verificación?
Key theories
- Equivalencia de autómatas finitos deterministas y no deterministas
- Todo autómata finito no determinista puede convertirse, mediante la construcción de subconjuntos, en uno determinista que acepte el mismo lenguaje, por lo que el no determinismo no añade poder de reconocimiento a nivel de estado finito, aunque puede ser exponencialmente más conciso.
- Teorema de Kleene
- Los lenguajes reconocidos por autómatas finitos son exactamente los lenguajes regulares descritos por expresiones regulares, uniendo las visiones de máquina, algebraica y gramatical de la clase de lenguaje más simple.
- La jerarquía de Chomsky
- Los lenguajes regulares, libres de contexto, sensibles al contexto y recursivamente enumerables forman una cadena de inclusión estricta, cada nivel emparejado con un tipo de gramática y con un modelo de autómata de estructura de memoria correspondiente.
Clinical relevance
Los autómatas finitos y las expresiones regulares impulsan el análisis léxico en compiladores, la búsqueda de texto y la especificación de protocolos, mientras que las gramáticas libres de contexto son la base del análisis sintáctico de lenguajes de programación; los autómatas sobre objetos infinitos forman el núcleo algorítmico de la verificación de modelos, donde un sistema se verifica contra una especificación de lógica temporal.
History
Los modelos de estados finitos surgieron de las redes neuronales de McCulloch y Pitts en la década de 1940 y Kleene les dio una forma teórica de lenguaje alrededor de 1951. Rabin y Scott introdujeron los autómatas no deterministas en 1959, mientras que las gramáticas de Chomsky de finales de la década de 1950 organizaron las clases de lenguajes en la jerarquía que aún estructura el tema.
Key figures
- Stephen Kleene
- Michael Rabin
- Dana Scott
- Noam Chomsky
Related topics
Seminal works
- rabinScott1959
- sipser2013
- hopcroft2006
Frequently asked questions
- ¿Por qué un autómata finito no puede reconocer paréntesis balanceados?
- Reconocer anidamientos arbitrariamente profundos requiere contar cuántas aperturas aún no tienen correspondencia, lo que puede exceder cualquier número fijo de estados. Un autómata finito solo tiene memoria limitada, por lo que esta capacidad de conteo se encuentra un nivel más arriba, con los autómatas de pila y los lenguajes libres de contexto.
- ¿Cuál es el beneficio práctico de la teoría de lenguajes formales?
- Indica a los ingenieros qué patrones puede expresar una herramienta determinada. Las expresiones regulares son suficientes para los tokens, pero no para la estructura anidada, razón por la cual los compiladores dividen el trabajo entre un analizador léxico regular y un analizador sintáctico libre de contexto, y por qué las herramientas de verificación se basan en autómatas sobre palabras infinitas.