Autómatas Finitos y Lenguajes Regulares

Los autómatas finitos son las máquinas computacionales más simples, que leen la entrada símbolo a símbolo utilizando solo un número limitado de estados internos, y los lenguajes que reconocen son precisamente los lenguajes regulares.

Definition

Un autómata finito es una máquina con un conjunto finito de estados, una función de transición sobre símbolos de entrada, un estado inicial y estados de aceptación; acepta una cadena si la lectura de la cadena lo lleva desde el estado inicial a un estado de aceptación, y el conjunto de cadenas aceptadas es su lenguaje.

Scope

Este tema abarca los autómatas finitos deterministas y no deterministas, su equivalencia mediante la construcción de subconjuntos, las expresiones regulares y el teorema de Kleene, el teorema de Myhill-Nerode y la minimización de estados, las propiedades de cierre de los lenguajes regulares y el lema de bombeo utilizado para demostrar que ciertos lenguajes no son regulares.

Core questions

• ¿Qué lenguajes pueden reconocerse utilizando solo una cantidad de memoria fija y finita?
• ¿Por qué los autómatas finitos deterministas y no deterministas son igualmente potentes?
• ¿Cómo se puede demostrar que un lenguaje específico no es regular?
• ¿Cuál es el autómata más pequeño que reconoce un lenguaje regular dado?

Key theories

Construcción de subconjuntos

Cualquier autómata finito no determinista puede ser simulado por uno determinista cuyos estados son conjuntos de los estados originales, lo que demuestra que ambos modelos reconocen exactamente los mismos lenguajes.

Teorema de Kleene

Un lenguaje es reconocido por un autómata finito si y solo si es descrito por una expresión regular, estableciendo la equivalencia de las descripciones de máquina y algebraicas de los lenguajes regulares.

Teorema de Myhill–Nerode

Un lenguaje es regular exactamente cuando su relación de indistinguibilidad de cadenas tiene un número finito de clases, y estas clases determinan el autómata determinista mínimo único para el lenguaje.

Clinical relevance

Los autómatas finitos son el motor detrás de la coincidencia de expresiones regulares, los escáneres y analizadores léxicos en los compiladores, la búsqueda y reemplazo en los editores de texto, y la detección de patrones en los sistemas de intrusión de red, donde el reconocimiento con memoria limitada hace que el procesamiento sea rápido y predecible.

History

Basándose en el modelo de redes neuronales de McCulloch y Pitts de 1943, Kleene caracterizó los eventos que los autómatas finitos pueden representar alrededor de 1951, y Rabin y Scott formalizaron los autómatas no deterministas y sus problemas de decisión en 1959, trabajo que fue posteriormente reconocido con el Premio Turing.

Key figures

• Stephen Kleene
• Michael Rabin
• Dana Scott
• Anil Nerode

Seminal works

• rabinScott1959
• sipser2013

Frequently asked questions

¿Cómo se demuestra que un lenguaje no es regular?

La herramienta más común es el lema de bombeo, que establece que toda cadena suficientemente larga en un lenguaje regular contiene una subcadena que puede repetirse cualquier número de veces mientras permanece en el lenguaje. Encontrar una cadena que no pueda ser 'bombeada' de esta manera demuestra que el lenguaje no es regular; el teorema de Myhill-Nerode ofrece un argumento alternativo al exhibir infinitos prefijos distinguibles.

Si los autómatas no deterministas no son más potentes, ¿por qué utilizarlos?

A menudo son mucho más pequeños y fáciles de diseñar o de derivar de una expresión regular. La construcción de subconjuntos puede convertirlos a una forma determinista cuando sea necesario, con un posible costo exponencial en el número de estados, por lo que el no determinismo es una herramienta de especificación conveniente más que un aumento en el poder de reconocimiento.