Teoría de autómatas

Estudio de máquinas abstractas y autómatas.

Clases de autómatas

El autómata descrito en este diagrama de estados 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 ₁ hasta sí mismo contienen un número par de flechas marcadas con 0, este autómata acepta cadenas que contienen un número par de 0.

La teoría de autómatas es el estudio de las máquinas abstractas y los autómatas , así como de los problemas computacionales que se pueden resolver mediante su uso. Es una teoría de la informática teórica con estrechas conexiones con la lógica matemática . La palabra autómata proviene de la palabra griega αὐτόματος, que significa "autoactivo, voluntario, automóvil". Un autómata (autómatas en plural) es un dispositivo informático abstracto autopropulsado que sigue una secuencia predeterminada de operaciones de forma automática. 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 es un tipo bien conocido de autómata. 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, realiza 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 autómatas está estrechamente relacionada con la teoría de lenguajes formales . En este contexto, los autómatas se utilizan como representaciones finitas de lenguajes formales que pueden ser infinitos. Los autómatas se clasifican a menudo por la clase de lenguajes formales que pueden reconocer, como en la jerarquía de Chomsky , que describe una relación de anidación entre las principales clases de autómatas. Los autómatas desempeñan un papel importante en la teoría de la computación , la construcción de compiladores , la inteligencia artificial , el análisis sintáctico y la verificación formal .

Historia

La teoría de autómatas abstractos fue desarrollada a mediados del siglo XX en conexión con los autómatas finitos . ^[1] La teoría de autómatas fue considerada inicialmente una rama de la teoría de sistemas matemáticos , que estudia el comportamiento de los sistemas de parámetros discretos. Los primeros trabajos en la teoría de autómatas diferían de los trabajos anteriores 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. ^[2] La teoría del transductor de estados finitos fue desarrollada con diferentes nombres por diferentes comunidades de investigación. ^[3] El concepto anterior de máquina de Turing también se incluyó en la disciplina junto con nuevas formas de autómatas de estados infinitos, como los autómatas de empuje .

En 1956 se publicó Automata Studies , que recogía trabajos de científicos como Claude Shannon , W. Ross Ashby , John von Neumann , Marvin Minsky , Edward F. Moore y Stephen Cole Kleene . ^[4] Con la publicación de este volumen, «la teoría de autómatas surgió como una disciplina relativamente autónoma». ^[5] El libro incluía la descripción de Kleene del conjunto de eventos regulares, o lenguajes regulares , y una medida relativamente estable de la complejidad en los programas de máquinas de Turing de Shannon. ^[6] Ese mismo año, Noam Chomsky describió la jerarquía de Chomsky , una correspondencia entre autómatas y gramáticas formales , ^[7] 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 acotados condujo al teorema de Myhill-Nerode ^[8] , 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 demostrado en este período por Michael O. Rabin y Dana Scott , junto con la equivalencia computacional de autómatas finitos deterministas y no deterministas. ^[9]

En la década de 1960, surgió un conjunto de resultados algebraicos conocidos 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 mediante interconexión. ^[10] Si bien cualquier autómata finito puede simularse 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. ^[5] La teoría de la complejidad computacional también tomó forma en la década de 1960. ^{[11] [12]} A fines de la década, la teoría de autómatas comenzó a considerarse como "la matemática pura de la informática". ^[5]

Autómatas

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 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. ^[5]

Descripción informal

Un autómata se ejecuta cuando se le da una secuencia de entradas en pasos de tiempo discretos (individuales) (o simplemente pasos ). Un autómata procesa una entrada elegida de un conjunto de símbolos o letras , que se llama 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 está 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 a partir 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 realiza transiciones entre estados 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 llama estado final .

Para investigar las posibles secuencias de estados/entradas/salidas en un autómata usando 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 lenguaje es una cerradura electrónica , que acepta o rechaza los intentos de ingresar el código correcto.

Definición formal

Autómata

Un autómata puede representarse formalmente mediante un quíntuple , 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 alfabeto de salida del autómata,
• ${\displaystyle Q}$es un conjunto de estados ,
• ${\displaystyle \delta }$es la función de siguiente estado o función de transición que asigna pares de estado-entrada a estados sucesores, ${\displaystyle \delta :Q\times \Sigma \to Q}$
• ${\displaystyle \lambda }$es la función de siguiente salida que asigna pares de entrada-estado a salidas. ${\displaystyle \lambda :Q\times \Sigma \to \Gamma }$

Si es finito, entonces es un autómata finito . ^[5] ${\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 denota por . ${\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 está en el estado inicial , y recibe la entrada . Para y 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 a 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 . ${\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 extiende inductivamente a para describir el comportamiento de la máquina cuando se le introducen 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, . ^[10] La función de salida se puede extender de manera similar a , que proporciona la salida completa de la máquina cuando se ejecuta en la palabra del estado . ${\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 lenguajes formales , un autómata puede considerarse como un 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 la 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}$

Idioma reconocido

El lenguaje reconocido por un autómata es el conjunto de todas las palabras que son aceptadas por el autómata, . ^[13] ${\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 reconoce algún autómata. Para los autómatas finitos los lenguajes reconocibles son los lenguajes regulares . Para los distintos 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 el formalismo matemático. Por lo tanto, la definición de un autómata está abierta a variaciones según la "máquina del mundo real" que queramos modelar utilizando el autómata. La gente ha estudiado muchas variaciones de autómatas. A continuación, se presentan algunas variaciones populares en la definición de diferentes componentes de los autómatas.

Aporte

• Entrada finita : autómata que acepta solo secuencias finitas de símbolos. La definición introductoria anterior solo abarca palabras finitas.
• Entrada infinita : Autómata que acepta infinitas palabras ( ω-palabras ). Estos autómatas se denominan ω-autómatas .
• Entrada 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 una de esas copias comienza a ejecutarse en uno de los símbolos sucesores a partir del estado de acuerdo con la relación de transición del autómata. Un autómata de este tipo se denomina autómata de árbol .
• Entrada de árbol infinito  : las dos extensiones anteriores se pueden combinar, de modo que el autómata lea una estructura de árbol con ramas (in)finitas. Un autómata de este tipo se denomina 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 . ^[10]
• Estados finitos : Un autómata que contiene sólo un número finito de estados.
• Estados infinitos : Autómata que no puede tener un número finito de estados, ni siquiera un número contable de estados. Se pueden utilizar distintos 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 insertar y extraer símbolos. Este tipo de autómata se denomina autómata de inserción .
• Memoria de cola : un autómata puede tener memoria en forma de cola . Este tipo de máquina se denomina máquina de cola y es Turing-completa.
• Memoria en cinta : Las entradas y salidas de los autómatas suelen describirse como cintas de entrada y salida . Algunas máquinas tienen cintas de trabajo adicionales , entre ellas la máquina de Turing , el autómata lineal limitado y el transductor de espacio logarítmico .

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 un solo 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 permita su relación de transición. 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 a la de los autómatas 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 alternantes . La condición de aceptación debe cumplirse en todas las ejecuciones de dichas copias para aceptar la entrada.
• Bidireccionalidad : los autómatas pueden leer su entrada de izquierda a derecha, o pueden moverse hacia adelante y hacia atrás en la entrada, de manera similar a una máquina de Turing . Los autómatas que pueden moverse hacia adelante y hacia atrás en la entrada se denominan autómatas finitos bidireccionales .

Condición de aceptación

• Aceptación de palabras finitas : Igual que la descrita en la definición informal anterior.
• Aceptación de palabras infinitas : un ω-autómata no puede tener estados finales, ya que las palabras infinitas nunca terminan. En cambio, la aceptación de la palabra se decide observando 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 cierta probabilidad entre cero y uno. Por ejemplo, los autómatas finitos cuánticos , los autómatas geométricos y los autómatas métricos tienen aceptación probabilística.

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

La teoría de autómatas es una disciplina que estudia las propiedades de varios tipos de autómatas. Por ejemplo, las siguientes preguntas se estudian sobre un tipo determinado de autómata.

• ¿Qué clase de lenguajes formales es reconocible por algún tipo de autómata? (Lenguajes reconocibles)
• ¿Se encuentran ciertos autómatas cerrados bajo la unión, intersección o complementación de lenguajes formales? (Propiedades de clausura)
• ¿Qué tan expresivo es un tipo de autómata en términos de reconocer una clase de lenguajes formales? ¿Y cuál es su poder expresivo relativo? (Jerarquía del lenguaje)

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

• ¿Un autómata acepta al menos una 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 reconocido? (Determinización)
• Para un lenguaje formal dado, ¿cuál es el autómata más pequeño que lo reconoce? ( Minimización )

Tipos 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 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.

Jerarquía en términos de poderes

La siguiente es una jerarquía incompleta en términos de las capacidades de los diferentes tipos de máquinas virtuales. La jerarquía refleja las categorías anidadas de lenguajes que las máquinas pueden aceptar. ^[14]

Aplicaciones

Cada modelo en la teoría de autómatas juega papeles importantes en varias áreas aplicadas. Los autómatas finitos se utilizan en procesamiento de texto , compiladores y diseño de hardware . Las gramáticas libres de contexto (CFG) se utilizan en lenguajes de programación e inteligencia artificial. Originalmente, las CFG se usaban 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 usando la teoría de autómatas en biología incluyen el crecimiento de moluscos y piñas y los patrones de pigmentación. 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. ^[15] Otro problema para el cual 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 se puede definir en un lenguaje simbólico o su especificación se puede introducir en un formato prediseñado o se puede dibujar su diagrama de transición haciendo clic y arrastrando el ratón. Entre los simuladores de autómatas más conocidos se encuentran Turing's World, JFLAP, VAS, TAGS y SimStudio. ^[16]

Modelos de teoría de categorías

Se pueden definir varias categorías distintas de autómatas ^[17] siguiendo la clasificación de autómatas en diferentes tipos descrita 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 cartesiana cerrada ^[18] , tiene tanto límites categóricos como colímites . Un homomorfismo de autómatas mapea un quíntuple de un autómata A _i sobre el quíntuple de otro autómata A _j . Los homomorfismos de autómatas también pueden considerarse como transformaciones de autómatas o como homomorfismos de semigrupos , 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 autómatas en categorías monoidales ^{[19] [20] [21} ]

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 variables . 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 2-categoría , y también una subcategoría de la 2-categoría de grupoides, o la categoría de grupoide. ${\displaystyle A_{i}\to A_{i}}$

Véase también

• Cálculo diferencial booleano
• Red de Petri

Referencias

1. Mahoney, Michael S. "Las estructuras de la computación y la estructura matemática de la naturaleza". The Rutherford Journal . Consultado el 7 de junio de 2020 .
2. Booth, Taylor (1967). Máquinas secuenciales y teoría de autómatas . Nueva York: John Wiley & Sons. págs. 1-13. ISBN. 0-471-08848-X.
3. Ashby, William Ross (15 de enero de 1967). "El lugar del cerebro en el mundo natural" (PDF) . Currents in Modern Biology . 1 (2): 95–104. doi :10.1016/0303-2647(67)90021-4. PMID  6060865. Archivado desde el original (PDF) el 4 de junio de 2023 . Consultado el 29 de marzo de 2021 .:"Las teorías, ahora bien desarrolladas, de la "máquina de estados finitos" (Gill, 1962), del "transductor silencioso" (Shannon y Weaver, 1949), del "sistema determinado por el estado" (Ashby, 1952) y del "circuito secuencial", son esencialmente homólogas."
4. Ashby, WR; et al. (1956). CE Shannon; J. McCarthy (eds.). Estudios de autómatas . Princeton, NJ: Princeton University Press.
5. Arbib, Michael (1969). Teorías de autómatas abstractos . Englewood Cliffs, Nueva Jersey: Prentice-Hall.
6. Li, Ming; Paul, Vitanyi (1997). Introducción a la complejidad de Kolmogorov y sus aplicaciones . Nueva York: Springer-Verlag. pág. 84.
7. Chomsky, Noam (1956). "Tres modelos para la descripción del lenguaje" (PDF) . IRE Transactions on Information Theory . 2 (3): 113–124. doi :10.1109/TIT.1956.1056813. S2CID  19519474. Archivado (PDF) desde el original el 7 de marzo de 2016.
8. Nerode, A. (1958). "Transformaciones de autómatas lineales". Actas de la American Mathematical Society . 9 (4): 541. doi : 10.1090/S0002-9939-1958-0135681-9 .
9. Rabin, Michael ; Scott, Dana (abril de 1959). "Autómatas finitos y sus problemas de decisión" (PDF) . IBM Journal of Research and Development . 3 (2): 114–125. doi :10.1147/rd.32.0114. Archivado desde el original el 14 de diciembre de 2010.{{cite journal}}: CS1 maint: URL no apta ( enlace )
10. Hartmanis, J. ; Stearns, RE (1966). Teoría de la estructura algebraica de máquinas secuenciales . Englewood Cliffs, NJ: Prentice-Hall.
11. Hartmanis, J.; Stearns, RE (1964). "Complejidad computacional de secuencias recursivas" (PDF) .
12. Fortnow, Lance; Homer, Steve (2002). "Una breve historia de la complejidad computacional" (PDF) .
13. Moore, Cristopher (31 de julio de 2019). "Autómatas, lenguajes y gramáticas". arXiv : 1907.12713 [cs.CC].
14. Yan, Song Y. (1998). Introducción a los lenguajes formales y la computación por máquina. Singapur: World Scientific Publishing Co. Pte. Ltd., págs. 155-156. ISBN 978-981-02-3422-5.
15. Ferraguti, A.; Micheli, G.; Schnyder, R. (2018), Composiciones irreducibles de polinomios de grado dos sobre cuerpos finitos tienen estructura regular , The Quarterly Journal of Mathematics, vol. 69, Oxford University Press, págs. 1089–1099, arXiv : 1701.06040 , doi : 10.1093/qmath/hay015, S2CID  3962424
16. Chakraborty, P.; Saxena, PC; Katti, CP (2011). "Cincuenta años de simulación de autómatas: una revisión". ACM Inroads . 2 (4): 59–70. doi :10.1145/2038876.2038893. S2CID  6446749.
17. Jirí Adámek y Věra Trnková . 1990. Autómatas y Álgebras en Categorías . Editorial académica Kluwer: Dordrecht y Praga
18. Mac Lane, Saunders (1971). Categorías para el matemático en activo . Nueva York: Springer. ISBN 978-0-387-90036-0.
19. http://www.math.cornell.edu/~worthing/asl2010.pdf James Worthington.2010.Determinación, olvido y autómatas en categorías monoidales. Reunión anual norteamericana de la ASL, 17 de marzo de 2010
20. Aguiar, M. y Mahajan, S.2010. "Functores monoidales, especies y álgebras de Hopf" .
21. Meseguer, J., Montanari, U.: 1990 Las redes de Petri son monoides. Información y computación 88 :105–155

Lectura adicional

• John E. Hopcroft ; Rajeev Motwani ; Jeffrey D. Ullman (2000). Introducción a la teoría de autómatas, lenguajes y computación (2.ª ed.). Pearson Education. ISBN 978-0-201-44124-6.
• Michael Sipser (1997). Introducción a la teoría de la computación . PWS Publishing. ISBN 978-0-534-94728-6.Primera parte: Autómatas y lenguajes, capítulos 1 y 2, págs. 29 a 122. Sección 4.1: Lenguajes decidibles, págs. 152 a 159. Sección 5.1: Problemas indecidibles de la teoría del lenguaje, págs. 172 a 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 matemáticas y sus aplicaciones. Vol. 25. Cambridge University Press . ISBN 978-0-521-30245-6.Zbl 0565.68046  .
• Anderson, James A. (2006). Teoría de 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 . Chapman and Hall Mathematics Series. Londres: Chapman & Hall . Zbl  0231.94041.
• John M. Howie (1991) Autómatas y lenguajes , 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. Cambridge University Press . ISBN 978-0-521-84425-3.Zbl1188.68177  .​
• James P. Schmeiser; David T. Barnard (1995). Generación de un orden de análisis de arriba hacia abajo con análisis de abajo hacia arriba . Elsevier North-Holland.
• Igor Aleksander y F. Keith Hanna (1975). Teoría de autómatas: un enfoque de ingeniería . Nueva York: Crane Russak. ISBN 978-0-8448-0657-0.
• Marvin Minsky (1967). Computación: máquinas finitas e infinitas . Princeton, NJ: Prentice Hall.
• John C. Martin (2011). Introducción a los lenguajes y la teoría de la computación . Nueva York: McGraw Hill. ISBN 978-0-07-319146-1.

Enlaces externos

• dk.brics.automaton
• libfa