autómatas

Los autómatas son modelos matemáticos de máquinas que procesan cadenas de símbolos y siguen reglas de transición para aceptar entradas o transformar información. Son pilares de la teoría de lenguajes formales y de la computación teórica, y permiten clasificar problemas por su poder de cómputo. Entre ellos destacan los autómatas finitos, los autómatas de pila y las máquinas de Turing, cada uno con capacidades distintas.

Los autómatas finitos, ya sean deterministas (DFA) o no deterministas (NFA), reconocen lenguajes regulares. En un DFA existe una única transición para cada símbolo desde cada estado; en un NFA pueden existir varias posibilidades. Aun así, DFAs y NFAs reconocen la misma clase de lenguajes, y cualquier NFA se puede convertir a un DFA mediante la construcción de conjuntos de estados. Las expresiones regulares describen exactamente estos lenguajes y, en conjunto, estos automátas muestran las propiedades de cierre bajo operaciones como unión, intersección y complemento.

Los autómatas de pila amplían la memoria con una pila, lo que les permite reconocer lenguajes libres de contexto. Existen versiones deterministas y no deterministas; son suficientes para describir la sintaxis de la mayoría de lenguajes de programación, aunque algunasgramáticas CFL requieren nondeterminismo para su reconocimiento en general.

Las máquinas de Turing constituyen el modelo de cálculo más general dentro de la computación teórica. Con una cinta infinita y un conjunto finito de estados, pueden simular cualquier algoritmo computable. Los lenguajes recursivamente enumerables son exactamente los que pueden ser reconocidos por estas máquinas; si además son decidibles, forman lenguajes recursivos. La tesis de Church–Turing afirma que cualquier modelo razonable de cómputo puede ser emulado por una máquina de Turing.

La teoría de autómatas tiene aplicaciones en compiladores, procesamiento de lenguaje natural, verificación de software y sistemas, diseño de hardware y verificación formal, y se organiza en la jerarquía de Chomsky: lenguajes regulares, libres de contexto, contextuales y recursivamente enumerables.