Teoría de los autómatas - Automata theory

Clases de autómatas

(Al hacer clic en cada capa se obtiene un artículo sobre ese tema)

El autómata descrito por este diagrama de estado comienza en el estado S ₁ , y cambia de estado siguiendo las flechas marcadas con 0 o 1 según los símbolos de entrada a medida que llegan. El círculo doble marca S ₁ como un estado de aceptación. Dado que todos los caminos desde S ₁ a sí mismo contienen un número par de flechas marcadas con 0, este autómata acepta cadenas que contienen números pares de 0.

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 con ellos. Es una teoría en informática teórica . La palabra autómata (el plural de autómata ) proviene de la palabra griega αὐτόματος, que significa "autoactiva, obstinada, auto-movida". Un autómata (Automata en plural) es un dispositivo informático autopropulsado abstracto 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 estados finitos (FSM).

La figura de la derecha ilustra una máquina de estados finitos , que pertenece a un tipo bien conocido de autómata. Este autómata consta de estados (representados en la figura por círculos) y transiciones (representados 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 el estado anterior y el símbolo de entrada actual como argumentos.

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 .

Historia

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 los autómatas se consideró inicialmente 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 se diferenciaron del trabajo anterior sobre sistemas al utilizar el á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 con diferentes nombres por diferentes comunidades de investigación. El concepto anterior de máquinas 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 emergió 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ó An Introduction to Cybernetics , un libro de texto accesible que explica los autómatas y la información utilizando la teoría de conjuntos básica.

El estudio de los autómatas lineales condujo al teorema de Myhill-Nerode , que da 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 conjunto 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 puede simularse utilizando un conjunto de puerta universal , esto requiere que el circuito de simulación contenga bucles de complejidad arbitraria. La teoría de la estructura se ocupa de la realizabilidad "libre de 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 "la matemática pura de la informática".

Autómatas

Lo que sigue es una definición general de autómata, que restringe una definición más amplia de sistema a uno visto como actuando 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.

Descripción informal

Un autómata se ejecuta cuando se le da alguna secuencia de entradas en pasos o pasos de tiempo discretos (individuales) . 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 una 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 una funció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 pasa de un estado a otro 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 , a una máquina se le puede asignar un estado inicial 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 un candado electrónico que acepta o rechaza los intentos de ingresar el código correcto.

Definicion formal

Autómata

Un autómata se puede representar formalmente mediante una tupla de 5 , donde: ${\ Displaystyle M = \ langle \ Sigma, \ Gamma, Q, \ delta, \ lambda \ rangle}$

• ${\ Displaystyle \ Sigma}$es un conjunto finito de símbolos , llamado alfabeto de entrada del autómata,
• ${\ Displaystyle \ Gamma}$es otro conjunto finito de símbolos, llamado el alfabeto de salida del autómata,
• ${\ displaystyle Q}$es un conjunto de estados ,
• ${\ Displaystyle \ delta}$es la función de estado siguiente o función de transición que mapea pares de entrada de estado a estados sucesores,${\ Displaystyle \ delta: Q \ times \ Sigma \ to Q}$
• ${\ Displaystyle \ lambda}$es la función de siguiente salida que asigna pares de entrada de estado a salidas.${\ Displaystyle \ lambda: Q \ times \ Sigma \ to \ Gamma}$

Si es finito, entonces es un autómata finito .${\ displaystyle Q}$${\ Displaystyle M}$

Palabra de entrada

Un autómata lee una cadena finita de símbolos , donde , que se denomina palabra de entrada . El conjunto de todas las palabras se indica con .${\ Displaystyle a_ {1} a_ {2} ... a_ {n}}$${\ Displaystyle a_ {i} \ in \ Sigma}$${\ Displaystyle \ Sigma ^ {*}}$

Correr

Una secuencia de estados , donde tal que para , es una ejecución del autómata en una entrada que comienza desde el estado . En otras palabras, al principio el autómata se encuentra en el estado de inicio y recibe una entrada . Por y cada siguiente en la cadena de entrada, el autómata recoge el siguiente estado de acuerdo con la función de transición , hasta que el último símbolo ha sido leído, dejando la máquina en el estado final de la carrera, . Del mismo modo, en cada paso, el autómata emite un símbolo de salida de acuerdo con la función de salida .${\ Displaystyle q_ {0}, q_ {1}, ... q_ {n}}$${\ Displaystyle q_ {i} \ in Q}$${\ Displaystyle q_ {i} = \ delta (q_ {i-1}, a_ {i})}$${\ Displaystyle 0 <i \ leq n}$${\ Displaystyle a_ {1} a_ {2} ... a_ {n} \ in \ Sigma ^ {*}}$${\ Displaystyle q_ {0}}$${\ Displaystyle q_ {0}}$${\ Displaystyle a_ {1}}$${\ Displaystyle a_ {1}}$${\ Displaystyle a_ {i}}$${\ Displaystyle q_ {i}}$${\ Displaystyle \ delta (q_ {i-1}, a_ {i})}$${\ Displaystyle a_ {n}}$${\ Displaystyle q_ {n}}$${\ Displaystyle \ lambda (q_ {i-1}, a_ {i})}$

La función de transición se amplía inductivamente para describir el comportamiento de la máquina cuando se alimentan palabras de entrada completas. Para la cadena vacía , para todos los estados , y para cuerdas , donde es el último símbolo y es el (posiblemente vacía) resto de la cadena, . La función de salida se puede extender de manera similar a , lo que proporciona la salida completa de la máquina cuando se ejecuta en word from state .${\ Displaystyle \ delta}$${\ Displaystyle {\ overline {\ delta}}: Q \ times \ Sigma ^ {*} \ to Q}$${\ Displaystyle \ varepsilon}$${\ Displaystyle {\ overline {\ delta}} (q, \ varepsilon) = q}$${\ Displaystyle q}$${\ displaystyle wa}$${\ Displaystyle a}$${\ Displaystyle w}$${\ Displaystyle {\ overline {\ delta}} (q, wa) = \ delta ({\ overline {\ delta}} (q, w), a)}$${\ Displaystyle \ lambda}$${\ Displaystyle {\ overline {\ lambda}} (q, w)}$${\ Displaystyle w}$${\ Displaystyle q}$

Aceptador

Para estudiar un autómata con la teoría de los lenguajes formales , un autómata puede ser considerado como aceptor , reemplazando el alfabeto y la función de salida y con ${\ Displaystyle \ Gamma}$${\ Displaystyle \ lambda}$

• ${\ Displaystyle q_ {0} \ in Q}$, un estado de inicio designado , y
• ${\ Displaystyle F}$, un conjunto de estados de (es decir ) llamados estados de aceptación .${\ displaystyle Q}$${\ Displaystyle F \ subseteq Q}$

Esto permite definir lo siguiente:

Aceptando palabra

Una 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 está en un estado de aceptación.${\ Displaystyle w = a_ {1} a_ {2} ... a_ {n} \ in \ Sigma ^ {*}}$${\ Displaystyle {\ overline {\ delta}} (q_ {0}, w) \ in F}$${\ Displaystyle w}$

Lenguaje reconocido

El lenguaje reconocido por un autómata es el conjunto de todas las palabras que son aceptadas por el autómata, .${\ Displaystyle L \ subseteq \ Sigma ^ {*}}$ ${\ Displaystyle L = \ {w \ in \ Sigma ^ {*} \ | \ {\ overline {\ delta}} (q_ {0}, w) \ in F \}}$

Idiomas reconocibles

Los lenguajes reconocibles son el conjunto de lenguajes que son reconocidos por algún autómata. Para los autómatas finitos, los lenguajes reconocibles son lenguajes regulares . Para diferentes tipos de autómatas, los lenguajes reconocibles son diferentes.

Definiciones variantes de autómatas

Los autómatas se definen para estudiar máquinas útiles bajo formalismo matemático. Entonces, la definición de un autómata está abierta a variaciones según la "máquina del mundo real", que queremos modelar utilizando 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

• Entrada finita : un autómata que acepta solo una secuencia finita de símbolos. La definición introductoria anterior solo abarca palabras finitas.
• Entrada infinita : un autómata que acepta palabras infinitas (palabras ω ). Estos autómatas se denominan ω-autómatas .
• Entrada de palabra de árbol : la entrada puede ser un árbol de símbolos en lugar de una secuencia de símbolos. En este caso, después de leer cada símbolo, el autómata lee todos los símbolos sucesores en el árbol de entrada. Se dice que el autómata hace una copia de sí mismo para cada sucesor y cada copia comienza a ejecutarse en uno de los símbolos sucesores del estado de acuerdo con la relación de transición del autómata. Tal autómata se llama árbol autómata .
• Entrada de árbol infinito  : las dos extensiones anteriores se pueden combinar, por lo que el autómata lee una estructura de árbol con ramas finitas (in). Tal autómata se llama autómata de árbol infinito

Estados

• Estado único : un autómata con un estado, también llamado circuito combinacional , realiza una transformación que puede implementar lógica combinacional .
• Estados finitos : un autómata que contiene solo un número finito de estados.
• Estados infinitos : un autómata que puede no tener un número finito de estados, o incluso un número contable de estados. Se pueden utilizar diferentes tipos de memoria abstracta para dar a estas máquinas descripciones finitas.
• Memoria de pila : un autómata también puede contener algo de memoria adicional en forma de pila en la que se pueden empujar y hacer estallar símbolos. Este tipo de autómata se llama autómata de empuje.
• Memoria de cola : un autómata puede tener memoria en forma de cola . Tal máquina se llama máquina de cola y es Turing-completa.
• Memoria de cinta : las entradas y salidas de los autómatas a menudo se describen como cintas de entrada y salida . Algunas máquinas tienen cintas de trabajo adicionales , incluida la máquina de Turing , el autómata delimitado lineal y el transductor de espacio de registro .

Función de transición

• Determinista : para un estado actual dado y un símbolo de entrada, si un autómata solo puede saltar a uno y solo a un estado, entonces es un autómata determinista .
• No determinista : un autómata que, después de leer un símbolo de entrada, puede saltar a cualquiera de varios estados, según lo autorizado por su relación de transición. Observe que el término función de transición se reemplaza por relación de transición: el autómata decide de manera no determinista saltar a una de las opciones permitidas. Estos autómatas se denominan autómatas no deterministas .
• Alternancia : esta idea es bastante similar al autómata de árbol, pero ortogonal. El autómata puede ejecutar sus múltiples copias en el mismo símbolo de lectura siguiente. Estos autómatas se denominan autómatas alternos . La condición de aceptación debe satisfacer todas las ejecuciones de dichas copias para aceptar la entrada.

Condición de aceptación

• Aceptación de palabras finitas : Igual que se describe en la definición informal anterior.
• Aceptación de palabras infinitas : un autómata omega no puede tener estados finales, ya que las palabras infinitas nunca terminan. Más bien, la aceptación de la palabra se decide al observar la secuencia infinita de estados visitados durante la ejecución.
• Aceptación probabilística : un autómata no necesita aceptar o rechazar estrictamente una entrada. Puede aceptar la entrada con alguna probabilidad entre cero y uno. Por ejemplo, el autómata cuántico finito, el autómata geométrico y el autómata métrico tienen aceptación probabilística.

Las diferentes combinaciones de las variaciones anteriores producen muchas clases de autómatas.

La teoría de los 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.

• ¿Qué clase de lenguajes formales es reconocible por algún tipo de autómata? (Idiomas reconocibles)
• ¿Se cierran ciertos autómatas bajo unión, intersección o complementación de lenguajes formales? (Propiedades de cierre)
• ¿Qué tan expresivo es un tipo de autómatas en términos de reconocer una clase de lenguajes formales? ¿Y su relativo poder expresivo? (Jerarquía de idiomas)

La teoría de los autómatas también estudia la existencia o no existencia de algoritmos efectivos para resolver problemas similares a la siguiente lista:

• ¿Acepta un autómata alguna palabra de entrada? (Comprobación de vacío)
• ¿Es posible transformar un autómata no determinista dado en un autómata determinista sin cambiar el lenguaje reconocible? (Determinación)
• Para un lenguaje formal dado, ¿cuál es el autómata más pequeño que lo reconoce? ( Minimización )

Clases de autómatas

La siguiente es una lista incompleta de tipos de autómatas.

Autómatas discretos, continuos e híbridos

Normalmente, la teoría de autómatas describe los estados de las máquinas abstractas, pero hay autómatas discretos, autómatas analógicos o autómatas continuos , o autómatas discretos-continuos híbridos , que utilizan datos digitales, datos analógicos o tiempo continuo, o datos digitales y analógicos, respectivamente.

Jerarquía en términos de poderes

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 idiomas que las máquinas pueden aceptar.

Aplicaciones

Cada modelo en la teoría de autómatas juega un papel importante en varias áreas aplicadas. Los autómatas finitos se utilizan en 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 , el famoso ejemplo más siendo John Conway 's juego de la vida . Algunos otros ejemplos que podrían explicarse usando la teoría de autómatas en biología incluyen patrones de pigmentación y crecimiento de conos de pino y moluscos. Yendo más allá, algunos científicos defienden una teoría que sugiere que todo el universo es calculado 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 . Los autómatas también aparecen en la teoría de campos finitos: el conjunto de polinomios irreducibles que se pueden escribir como composición de polinomios de grado dos es de hecho un lenguaje regular. Otro problema para el que se pueden utilizar autómatas es la inducción de lenguajes regulares .

Simuladores de autómatas

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 puede definirse en un lenguaje simbólico o su especificación puede ingresarse en una forma prediseñada o su diagrama de transición puede dibujarse haciendo clic y arrastrando el mouse. Los simuladores de autómatas más conocidos incluyen Turing's World, JFLAP, VAS, TAGS y SimStudio.

Conexión con la teoría de categorías

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 colimits. Un homomorfismo de autómatas mapea un quintuple de un autómata A _i sobre el quintuple 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 semigrupo, cuando el espacio de estados, S , del autómata se define como un semigrupo S _g . Los monoides también se consideran un entorno adecuado para los 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 sobre 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 tipos complejos no deterministas, o de otro tipo de autómatas, el último conjunto de endomorfismos puede llegar a ser, sin embargo, un autómata variable de groupoid . Por lo tanto, en el caso más general, las categorías de autómatas variables de cualquier tipo son categorías de agrupaciones o categorías de agrupaciones . 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 grupoides, o la categoría grupoide. ${\ Displaystyle A_ {i} \ to A_ {i}}$

Ver también

• Cálculo diferencial booleano

Referencias

Otras lecturas

• John E. Hopcroft , Rajeev Motwani , Jeffrey D. Ullman (2000). Introducción a la teoría, los lenguajes y la computación de los autómatas (2ª ed.). Educación Pearson. ISBN 978-0-201-44124-6.Mantenimiento de CS1: utiliza el parámetro de autores ( enlace )
• Michael Sipser (1997). Introducción a la Teoría de la Computación . Publicación de PWS. ISBN 978-0-534-94728-6.Primera parte: Autómatas y lenguajes, capítulos 1–2, págs. 29–122. Sección 4.1: Lenguajes decidibles, págs. 152-159. Sección 5.1: Problemas indecidibles de la teoría del lenguaje, págs. 172-183.
• Elaine Rich (2008). Autómatas, Computabilidad y Complejidad: Teoría y Aplicaciones . Pearson. ISBN 978-0-13-228806-4.
• Salomaa, Arto (1985). Computación y autómatas . Enciclopedia de las matemáticas y sus aplicaciones. 25 . Prensa de la Universidad de Cambridge . ISBN 978-0-521-30245-6. Zbl  0565.68046 .
• Anderson, James A. (2006). Teoría de los autómatas con aplicaciones modernas . Con contribuciones de Tom Head. Cambridge: Cambridge University Press . ISBN 978-0-521-61324-8. Zbl  1127.68049 .
• Conway, JH (1971). Álgebra regular y máquinas finitas . Serie de matemáticas de Chapman y Hall. Londres: Chapman & Hall . Zbl  0231.94041 .
• John M. Howie (1991) Autómatas e idiomas , Clarendon Press ISBN  0-19-853424-8 MR 1254435
• Sakarovitch, Jacques (2009). Elementos de la teoría de autómatas . Traducido del francés por Reuben Thomas. Prensa de la Universidad de Cambridge . ISBN 978-0-521-84425-3. Zbl  1188.68177 .
• James P. Schmeiser , David T. Barnard (1995). Producir un orden de análisis de arriba hacia abajo con análisis de abajo hacia arriba . Elsevier Holanda Septentrional.Mantenimiento de CS1: utiliza el parámetro de autores ( enlace )
• Igor Aleksander , F. Keith Hanna (1975). Teoría de los autómatas: un enfoque de ingeniería . Nueva York: Crane Russak. ISBN 978-0-8448-0657-0.Mantenimiento de CS1: utiliza el parámetro de autores ( enlace )
• Marvin Minsky (1967). Computación: Máquinas finitas e infinitas . Princeton, Nueva Jersey: Prentice Hall.
• John C. Martin (2011). Introducción a los lenguajes y teoría de la computación . Nueva York, NY 10020: McGraw Hill. ISBN 978-0-07-319146-1.Mantenimiento de CS1: ubicación ( enlace )

enlaces externos

• Visual Automata Simulator , una herramienta para simular, visualizar y transformar autómatas de estado finito y máquinas de Turing, por Jean Bovet
• JFLAP
• dk.brics.automaton
• libfa