Iteración
(leer más)
La teoría de los autómatas es el estudio de las máquinas abstractas y los autómatas, así como los problemas computacionales que se pueden resolver usándolos. Es una teoría en informática teórica. La palabra autómataproviene de la palabra griega αὐτόματος, que significa "autoactuación, voluntad propia, movimiento propio". Un autómata (autómata en plural) es un dispositivo informático abstracto autopropulsado que sigue una secuencia predeterminada de operaciones automáticamente. Un autómata con un número finito de estados se denomina autómata finito (FA) o máquina de estado finito (FSM). La figura de la derecha ilustra una máquina de estados finitos, que es un tipo de autómata bien conocido. Este autómata consta de estados (representados en la figura por círculos) y transiciones (representadas por flechas). Cuando el autómata ve un símbolo de entrada, hace una transición (o salto) a otro estado, de acuerdo con su función de transición, que toma como argumentos el estado anterior y el símbolo de entrada actual.
La teoría de los autómatas está estrechamente relacionada con la teoría del lenguaje formal. En este contexto, los autómatas se utilizan como representaciones finitas de lenguajes formales que pueden ser infinitos. Los autómatas a menudo se clasifican por la clase de lenguajes formales que pueden reconocer, como en la jerarquía de Chomsky, que describe una relación de anidamiento entre las principales clases de autómatas. Los autómatas juegan un papel importante en la teoría de la computación, la construcción de compiladores, la inteligencia artificial, el análisis y la verificación formal.
La teoría de los autómatas abstractos se desarrolló a mediados del siglo XX en relación con los autómatas finitos. La teoría de autómatas se consideró inicialmente como una rama de la teoría de sistemas matemáticos, que estudiaba el comportamiento de los sistemas de parámetros discretos. Los primeros trabajos en la teoría de los autómatas diferían de los trabajos anteriores sobre sistemas en el uso del álgebra abstracta para describir los sistemas de información en lugar del cálculo diferencial para describir los sistemas materiales. La teoría del transductor de estado finito fue desarrollada bajo diferentes nombres por diferentes comunidades de investigación. El concepto anterior de máquina de Turing también se incluyó en la disciplina junto con nuevas formas de autómatas de estado infinito, como los autómatas pushdown.
1956 vio la publicación de Automata Studies, que recopiló el trabajo de científicos como Claude Shannon, W. Ross Ashby, John von Neumann, Marvin Minsky, Edward F. Moore y Stephen Cole Kleene. Con la publicación de este volumen, "la teoría de los autómatas surgió como una disciplina relativamente autónoma". El libro incluía la descripción de Kleene del conjunto de eventos regulares, o lenguajes regulares, y una medida relativamente estable de complejidad en los programas de la máquina de Turing de Shannon. En el mismo año, Noam Chomsky describió la jerarquía de Chomsky, una correspondencia entre autómatas y gramáticas formales, y Ross Ashby publicó Introducción a la cibernética, un libro de texto accesible que explica los autómatas y la información utilizando la teoría básica de conjuntos.
El estudio de los autómatas acotados lineales condujo al teorema de Myhill-Nerode, que proporciona una condición necesaria y suficiente para que un lenguaje formal sea regular y un recuento exacto del número de estados en una máquina mínima para el lenguaje. El lema de bombeo para lenguajes regulares, también útil en pruebas de regularidad, fue probado en este período por Michael O. Rabin y Dana Scott, junto con la equivalencia computacional de autómatas finitos deterministas y no deterministas.
En la década de 1960, surgió un cuerpo de resultados algebraicos conocido como "teoría de la estructura" o "teoría de la descomposición algebraica", que se ocupaba de la realización de máquinas secuenciales a partir de máquinas más pequeñas por interconexión. Si bien cualquier autómata finito se puede simular utilizando un conjunto de puertas universales, esto requiere que el circuito de simulación contenga bucles de complejidad arbitraria. La teoría de la estructura se ocupa de la realizabilidad "sin bucles" de las máquinas. La teoría de la complejidad computacional también tomó forma en la década de 1960. A finales de la década, la teoría de los autómatas pasó a ser vista como "las matemáticas puras de la informática".
Lo que sigue es una definición general de un autómata, que restringe una definición más amplia de un sistema a uno que actúa en pasos de tiempo discretos, con su comportamiento de estado y salidas definidas en cada paso por funciones inmutables de solo su estado y entrada.
Un autómata se ejecuta cuando se le da una secuencia de entradas en pasos de tiempo discretos (individuales) (o solo pasos). Un autómata procesa una entrada seleccionada de un conjunto de símbolos o letras, que se denomina alfabeto de entrada. Los símbolos recibidos por el autómata como entrada en cualquier paso son una secuencia de símbolos llamados palabras. Un autómata tiene un conjunto de estados. En cada momento durante la ejecución del autómata, el autómata se encuentra en uno de sus estados. Cuando el autómata recibe una nueva entrada, se mueve a otro estado (o transiciones) en función de unfunción de transición que toma el estado anterior y el símbolo de entrada actual como parámetros. Al mismo tiempo, otra función llamada función de salida produce símbolos del alfabeto de salida, también de acuerdo con el estado anterior y el símbolo de entrada actual. El autómata lee los símbolos de la palabra de entrada y cambia de estado hasta que la palabra se lee por completo, si tiene una longitud finita, momento en el que el autómata se detiene. Un estado en el que el autómata se detiene se denomina estado final.
Para investigar las posibles secuencias de estado/entrada/salida en un autómata utilizando la teoría del lenguaje formal, se puede asignar a una máquina un estado de inicio y un conjunto de estados de aceptación. Luego, dependiendo de si una ejecución que comienza desde el estado inicial termina en un estado de aceptación, se puede decir que el autómata acepta o rechaza una secuencia de entrada. El conjunto de todas las palabras aceptadas por un autómata se denomina lenguaje reconocido por el autómata. Un ejemplo familiar de una máquina que reconoce un idioma es una cerradura electrónica, que acepta o rechaza los intentos de ingresar el código correcto.
AutómataUn autómata se puede representar formalmente mediante una tupla de 5 , donde:
Si es finito, entonces es un autómata finito.Palabra de entradaUn autómata lee una cadena finita de símbolos , donde , que se denomina palabra de entrada. El conjunto de todas las palabras se denota por .CorrerUna secuencia de estados , donde tal que for , es una ejecución del autómata en una entrada a partir del estado . En otras palabras, al principio el autómata está en el estado inicial y recibe la entrada . Para cada uno de los siguientes en la cadena de entrada, el autómata elige el siguiente estado de acuerdo con la función de transición, hasta que se haya leído el último símbolo, dejando la máquina en el estado final de la ejecución,. De manera similar, en cada paso, el autómata emite un símbolo de salida de acuerdo con la función de salida.La función de transición se extiende inductivamente para describir el comportamiento de la máquina cuando se alimenta con palabras de entrada completas. Para la cadena vacía , para todos los estados y para cadenas donde es el último símbolo y es el resto (posiblemente vacío) de la cadena, . La función de salida puede extenderse de manera similar a , lo que da la salida completa de la máquina cuando se ejecuta en word from state .AceptadorPara estudiar un autómata con la teoría de los lenguajes formales, se puede considerar un autómata como aceptor, reemplazando el alfabeto y la función de salida y con
Esto permite definir lo siguiente:Aceptando palabraUna palabra es una palabra de aceptación para el autómata si , es decir, si después de consumir toda la cadena la máquina se encuentra en estado de aceptación.Idioma reconocidoEl lenguaje reconocido por un autómata es el conjunto de todas las palabras que son aceptadas por el autómata,.Idiomas reconociblesLos lenguajes reconocibles son el conjunto de lenguajes que son reconocidos por algún autómata. Para autómatas finitos, los lenguajes reconocibles son lenguajes regulares. Para diferentes tipos de autómatas, los lenguajes reconocibles son diferentes.
Los autómatas se definen para estudiar máquinas útiles bajo el formalismo matemático. Entonces, la definición de un autómata está abierta a variaciones de acuerdo con la "máquina del mundo real" que queremos modelar usando el autómata. La gente ha estudiado muchas variaciones de autómatas. Las siguientes son algunas variaciones populares en la definición de diferentes componentes de autómatas.Aporte
estados
Función de transición
Condición de aceptación
Diferentes combinaciones de las variaciones anteriores producen muchas clases de autómatas.
La teoría de autómatas es un tema que estudia las propiedades de varios tipos de autómatas. Por ejemplo, se estudian las siguientes preguntas sobre un tipo dado de autómatas.
La teoría de autómatas también estudia la existencia o inexistencia de algoritmos efectivos para resolver problemas similares a la siguiente lista:
La siguiente es una lista incompleta de tipos de autómatas.
Autómata | Idiomas reconocibles |
---|---|
Máquina de estado finito no determinista/determinista (FSM) | idiomas regulares |
Autómata pushdown determinista (DPDA) | lenguajes deterministas libres de contexto |
Autómata pushdown (PDA) | lenguajes libres de contexto |
Autómata lineal acotado (LBA) | lenguajes sensibles al contexto |
máquina de Turing | lenguajes recursivamente enumerables |
Autómata determinista de Büchi | ω-límite de idiomas |
Autómata no determinista de Büchi | ω-lenguajes regulares |
Autómata Rabin, autómata Streett, autómata Parity, autómata Muller | |
autómata ponderado |
Normalmente, la teoría de los autómatas describe los estados de las máquinas abstractas, pero existen autómatas discretos, autómatas analógicos o autómatas continuos, o autómatas híbridos discretos-continuos, que utilizan datos digitales, datos analógicos o tiempo continuo, o datos digitales y analógicos, respectivamente.
La siguiente es una jerarquía incompleta en términos de poderes de diferentes tipos de máquinas virtuales. La jerarquía refleja las categorías anidadas de lenguajes que las máquinas pueden aceptar.
Autómata |
---|
Autómata finito determinista (DFA) -- Potencia mínima(misma potencia) (misma potencia)Autómata finito no determinista (NFA)(arriba es más débil) (abajo es más fuerte)Autómata de empuje hacia abajo determinista (DPDA-I)con 1 almacén de empuje hacia abajo Autómata de empuje hacia abajo no determinista (NPDA-I) con 1 almacén de empuje hacia abajo Autómata lineal delimitado (LBA) Autómata de empuje hacia abajo determinista (DPDA-II) con 2 almacenes de empuje hacia abajo Autómata de empuje hacia abajo no determinista (NPDA-II) con 2 almacenes de empuje hacia abajo Máquina de Turing determinista (DTM) Máquina de Turing no determinista (NTM) Máquina de Turing probabilística (PTM) Máquina de Turing multicinta (MTM) Máquina de Turing multidimensional |
Cada modelo en la teoría de autómatas juega un papel importante en varias áreas aplicadas. Los autómatas finitos se utilizan en el procesamiento de texto, compiladores y diseño de hardware. La gramática libre de contexto (CFG) se utiliza en lenguajes de programación e inteligencia artificial. Originalmente, los CFG se utilizaron en el estudio de los lenguajes humanos. Los autómatas celulares se utilizan en el campo de la vida artificial, siendo el ejemplo más famoso el Juego de la vida de John Conway. Algunos otros ejemplos que podrían explicarse utilizando la teoría de autómatas en biología incluyen patrones de pigmentación y crecimiento de moluscos y piñas. Yendo más allá, algunos científicos defienden una teoría que sugiere que todo el universo es computado por algún tipo de autómata discreto. La idea se originó en el trabajo de Konrad Zuse y fue popularizada en Estados Unidos por Edward Fredkin. Otro problema para el que se pueden utilizar los autómatas es la inducción de lenguajes regulares.
Los simuladores de autómatas son herramientas pedagógicas que se utilizan para enseñar, aprender e investigar la teoría de los autómatas. Un simulador de autómatas toma como entrada la descripción de un autómata y luego simula su funcionamiento para una cadena de entrada arbitraria. La descripción del autómata se puede introducir de varias formas. Un autómata se puede definir en un lenguaje simbólico o se puede ingresar su especificación en un formulario prediseñado o se puede dibujar su diagrama de transición haciendo clic y arrastrando el mouse. Los simuladores de autómatas más conocidos incluyen Turing's World, JFLAP, VAS, TAGS y SimStudio.
Se pueden definir varias categorías distintas de autómatas siguiendo la clasificación de autómatas en diferentes tipos descritos en la sección anterior. La categoría matemática de autómatas deterministas, máquinas secuenciales o autómatas secuenciales y máquinas de Turing con homomorfismos de autómatas que definen las flechas entre autómatas es una categoría cerrada cartesiana, tiene tanto límites categóricos como colímites. Un homomorfismo de autómatas mapea un quíntuple de un autómata A i en el quíntuple de otro autómata A j. Los homomorfismos de autómatas también se pueden considerar como transformaciones de autómatas o como homomorfismos de semigrupos, cuando el espacio de estado,S, del autómata se define como un semigrupo S g. Los monoides también se consideran una configuración adecuada para autómatas en categorías monoidales.Categorías de autómatas variables
También se podría definir un autómata variable, en el sentido de Norbert Wiener en su libro El uso humano de los seres humanos a través de los endomorfismos . Entonces se puede demostrar que tales homomorfismos de autómatas variables forman un grupo matemático. En el caso de autómatas no deterministas u otros tipos complejos, el último conjunto de endomorfismos puede convertirse, sin embargo, en un grupoide de autómatas variable. Por lo tanto, en el caso más general, las categorías de autómatas variables de cualquier tipo son categorías de grupoides o categorías de grupoides. Además, la categoría de autómatas reversibles es entonces una categoría 2, y también una subcategoría de la categoría 2 de groupoides, o la categoría groupoid.