teoría de 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 que recibe. El doble círculo 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 ceros.

La teoría de autómatas estudia las máquinas y autómatas abstractos , así como los problemas computacionales que pueden resolverse mediante ellos. Es una teoría de la informática teórica con estrechas conexiones con la ciencia cognitiva y la lógica matemática . La palabra autómata proviene del griego αὐτόματος, que significa "autoactivo, con voluntad propia, que se mueve por sí mismo". Un autómata (autómatas en plural) es un dispositivo de computación abstracto y autónomo que sigue automáticamente una secuencia predeterminada de operaciones. Un autómata con un número finito de estados se denomina autómata finito (AF) o máquina de estados finitos (MEF). La figura de la derecha ilustra una máquina de estados finitos, un tipo de autómata muy 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 el estado anterior y el símbolo de entrada actual como sus 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 suelen clasificarse según 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 desempeñan un papel fundamental 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 los autómatas abstractos se desarrolló a mediados del siglo XX en relación con los autómatas finitos . ^{[ 1 ]} La teoría de autómatas se consideró inicialmente una rama de la teoría de sistemas matemáticos , que estudiaba el comportamiento de sistemas de parámetros discretos. Los primeros trabajos en teoría de autómatas se diferenciaron de los trabajos previos sobre sistemas al utilizar álgebra abstracta para describir sistemas de información en lugar de cálculo diferencial para describir sistemas materiales. ^{[ 2 ]} La teoría del transductor de estados finitos se desarrolló bajo 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 pila .

En 1956 se publicó Automata Studies , que reunió 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 de complejidad relativamente estable en programas de máquinas de Turing por Shannon. ^{[ 6 ]} En el 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 explicaba los autómatas y la información utilizando la teoría básica de conjuntos .

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, así como un recuento exacto del número de estados en una máquina mínima para dicho lenguaje. El lema de bombeo para lenguajes regulares , también útil en las pruebas de regularidad, fue demostrado en este período por Michael O. Rabin y Dana Scott , junto con la equivalencia computacional de los 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 abordaban 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 universal de puertas lógicas , 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 ]} Hacia finales de la década, la teoría de autómatas llegó a ser vista como "las matemáticas puras de la informática". ^{[ 5 ]}

Autómatas

A continuación se presenta una definición general de autómata, que restringe una definición más amplia de sistema a aquel que actúa en pasos de tiempo discretos, con su comportamiento de estado y salidas definidos en cada paso por funciones inmutables que dependen únicamente de su estado y entrada. ^{[ 5 ]}

Descripción informal

Un autómata se ejecuta cuando se le proporciona 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 denomina alfabeto de entrada . Los símbolos que recibe el autómata como entrada en cada paso son una secuencia de símbolos llamada palabras . Un autómata tiene un conjunto de estados . En cada momento durante la ejecución del autómata, este se encuentra en uno de sus estados. Cuando el autómata recibe una nueva entrada, pasa a otro estado (o realiza una transición ) en función de una función de transición que toma como parámetros el estado anterior y el símbolo de entrada actual. Al mismo tiempo, otra función, denominada función de salida , produce símbolos del alfabeto de salida , también según 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 su longitud es finita, momento en el que el autómata se detiene . El estado en el que se detiene el autómata se denomina estado final .

Para investigar las posibles secuencias de estado/entrada/salida en un autómata mediante la teoría del lenguaje formal , se le puede asignar a la máquina 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 conocido de una máquina que reconoce un lenguaje es una cerradura electrónica , que acepta o rechaza los intentos de introducir el código correcto.

Definición formal

Autómata

Un autómata puede representarse formalmente mediante una quíntupla.

M=\langle \Sigma,\Gamma,Q,\delta,\lambda \rangle

, dónde:

$\Sigma$ es un conjunto finito de símbolos , llamado alfabeto de entrada del autómata,
$\Gamma$ es otro conjunto finito de símbolos, llamado alfabeto de salida del autómata,
$Q$ es un conjunto de estados ,
$\delta$ es la función de siguiente estado o función de transición $\delta :Q\times \Sigma \to Q$ mapeo de pares estado-entrada a estados sucesores,
$\lambda$ es la siguiente función de salida $\lambda :Q\times \Sigma \to \Gamma$ mapeo de pares estado-entrada a salidas.

Si

Q

es finito, entonces

M

es un autómata finito . ^{[ 5 ]}

Palabra de entrada: Un autómata lee una cadena finita de símbolos. $a_{1}a_{2}...a_{n}$ , dónde $a_{i}\in \Sigma$ , que se denomina palabra de entrada . El conjunto de todas las palabras se denota por $\Sigma ^{*}$ .

Correr: Una secuencia de estados $q_{0},q_{1},...,q_{n}$ , dónde $q_{i}\in Q$ de tal manera que $q_{i}=\delta (q_{i-1},a_{i})$ para $0<i\leq n$ , es una ejecución del autómata en una entrada $a_{1}a_{2}...a_{n}\in \Sigma ^{*}$ comenzando desde el estado $q_{0}$ En otras palabras, al principio el autómata está en el estado inicial. $q_{0}$ y recibe entrada $a_{1}$ . Para $a_{1}$ y cada uno de los siguientes $a_{i}$ En la cadena de entrada, el autómata elige el siguiente estado. $q_{i}$ según la función de transición $\delta (q_{i-1},a_{i})$ , hasta el último símbolo $a_{n}$ se ha leído, dejando la máquina en el estado final de la ejecución, $q_{n}$ De manera similar, en cada paso, el autómata emite un símbolo de salida de acuerdo con la función de salida. $\lambda (q_{i-1},a_{i})$ .

La función de transición $\delta$ se extiende inductivamente en ${\overline {\delta }}:Q\times \Sigma ^{*}\to Q$ para describir el comportamiento de la máquina cuando se le proporcionan palabras de entrada completas. Para la cadena vacía $\varepsilon$ , ${\overline {\delta }}(q,\varepsilon )=q$ para todos los estados $q$ y para cadenas $wa$ dónde $a$ es el último símbolo y $w$ es el resto de la cadena (posiblemente vacío), ${\overline {\delta }}(q,wa)=\delta ({\overline {\delta }}(q,w),a)$ . ^{[ 10 ]} La función de salida $\lambda$ puede extenderse de manera similar a ${\overline {\lambda }}(q,w)$ , que proporciona la salida completa de la máquina cuando se ejecuta en una palabra $w$ del estado $q$ .
Aceptador

Para estudiar un autómata con la teoría de los lenguajes formales , un autómata puede ser considerado como un aceptador , reemplazando el alfabeto de salida y la función

\Gamma

y

\lambda

con

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

Esto permite definir lo siguiente:

Aceptando palabra: Una palabra $w=a_{1}a_{2}...a_{n}\in \Sigma ^{*}$ es una palabra aceptable para el autómata si ${\overline {\delta }}(q_{0},w)\in F$ , es decir, si después de consumir toda la cadena $w$ La máquina se encuentra en estado de aceptación.

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

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 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 un formalismo matemático. Por lo tanto, la definición de autómata admite variaciones según la "máquina del mundo real" que se desee modelar. Se han estudiado muchas variaciones de autómatas. A continuación, se presentan algunas variaciones populares en la definición de los diferentes componentes de los autómatas.

Aporte

Entrada finita : Un autómata que solo acepta secuencias finitas 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 á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 crea una copia de sí mismo para cada sucesor y cada una de estas copias comienza a ejecutarse en uno de los símbolos sucesores desde el estado según la relación de transición del autómata. Este tipo de autómata 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. Dicho autómata se denomina autómata de árbol infinito .

Estados

Estado único : Un autómata con un solo estado, también llamado circuito combinacional , realiza una transformación que puede implementar lógica combinacional . ^{[ 10 ]}
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, ni siquiera un número contable . Se pueden utilizar diferentes tipos de memoria abstracta para proporcionar descripciones finitas a dichas máquinas.
Memoria de pila : Un autómata también puede contener 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 pila .
Memoria de cola : Un autómata puede tener memoria en forma de cola . Dicha máquina se denomina máquina de cola y es Turing-completa.
Memoria en cinta : Las entradas y salidas de los autómatas se suelen describir como cintas de entrada y salida . Algunas máquinas tienen cintas de trabajo adicionales , como la máquina de Turing , el autómata lineal acotado 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 único estado, entonces es un autómata determinista .
Autómata no determinista : Un autómata que, tras 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 forma no determinista saltar a una de las opciones permitidas. Dichos autómatas se denominan autómatas no deterministas .
Alternancia : Esta idea es bastante similar a la de los autómatas de árbol, pero es ortogonal. El autómata puede ejecutar sus múltiples copias sobre el mismo símbolo de lectura siguiente. Dichos 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 de un lado a otro sobre la entrada, de forma similar a una máquina de Turing . Los autómatas que pueden moverse de un lado a otro sobre la entrada se denominan autómatas finitos bidireccionales .

Condición de aceptación

Aceptación de palabras finitas : Igual que 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 analizando la secuencia infinita de estados visitados durante la ejecución.
Aceptación probabilística : Un autómata no necesita aceptar ni rechazar estrictamente una entrada. Puede aceptarla con una probabilidad entre cero y uno. Por ejemplo, los autómatas cuánticos finitos , los autómatas geométricos y los autómatas métricos presentan aceptación probabilística.

Las diferentes combinaciones de las variaciones anteriores dan lugar a muchas clases de autómatas.

La teoría de autómatas es una disciplina que estudia las propiedades de diversos tipos de autómatas. Por ejemplo, las siguientes preguntas se analizan en relación con un tipo específico de autómata.

¿Qué clase de lenguajes formales es reconocible por algún tipo de autómata? (Lenguajes reconocibles)
¿Ciertos autómatas son cerrados bajo la unión, la intersección o la complementación de lenguajes formales? (Propiedades de cierre)
¿Qué grado de expresividad tiene un tipo de autómata a la hora de reconocer una clase de lenguajes formales? ¿Y cuál es su poder expresivo relativo? (Jerarquía de lenguajes)

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

¿Acepta un autómata 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

A continuación se muestra 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 de la teoría de autómatas desempeña un papel importante en diversas áreas aplicadas. Los autómatas finitos se utilizan en el procesamiento de textos , compiladores y diseño de hardware . Las gramáticas libres de contexto (GLC) se emplean en lenguajes de programación e inteligencia artificial. Originalmente, las GLC se utilizaban en el estudio de los lenguajes humanos . Los autómatas celulares se emplean en el campo de la vida artificial , siendo el ejemplo más famoso el Juego de la Vida de John Conway . Otros ejemplos que podrían explicarse mediante la teoría de autómatas en biología incluyen el crecimiento de moluscos y piñas, así como los patrones de pigmentación. Además, algunos científicos defienden una teoría que sugiere que todo el universo se calcula mediante algún tipo de autómata discreto. Esta idea se originó en la obra 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 pueden escribirse 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 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 maneras. Un autómata se puede definir en un lenguaje simbólico , su especificación se puede introducir en un formulario prediseñado o su diagrama de transición se puede dibujar haciendo clic y arrastrando el ratón. Algunos simuladores de autómatas conocidos son Turing's World, JFLAP, VAS, TAGS y SimStudio. ^{[ 16 ]}

Modelos basados en la 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 límites categóricos y colímites . Un homomorfismo de autómatas mapea una quíntuple de un autómata A _i sobre la 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 sobre El uso humano de los seres humanos a través de los endomorfismos. $A_{i}\to A_{i}$ 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, este ú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 grupoides.

Véase también

Referencias

↑ 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 .
↑ 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.
↑ 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. Bibcode : 1967BiSys...1...95A . doi : 10.1016/0303-2647(67)90021-4 . PMID 6060865. Archivado del 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 sin ruido" (Shannon y Weaver, 1949), del "sistema determinado por el estado" (Ashby, 1952) y del "circuito secuencial" son esencialmente homólogas."
↑ Ashby, WR; et al. (1956). CE Shannon; J. McCarthy (eds.). Automata Studies . Princeton, NJ: Princeton University Press.
1 2 3 4 5 Arbib, Michael (1969). Teorías de autómatas abstractos . Englewood Cliffs, NJ: Prentice-Hall.
↑ Li, Ming; Paul, Vitanyi (1997). Una introducción a la complejidad de Kolmogorov y sus aplicaciones . Nueva York: Springer-Verlag. pág. 84.
↑ 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) del original el 7 de marzo de 2016.
↑ Nerode, A. (1958). "Transformaciones de autómatas lineales" . Actas de la Sociedad Matemática Americana . 9 (4): 541. doi : 10.1090/S0002-9939-1958-0135681-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 del original el 14 de diciembre de 2010.
1 2 3 Hartmanis, J. ; Stearns, RE (1966). Teoría de la estructura algebraica de las máquinas secuenciales . Englewood Cliffs, NJ: Prentice-Hall.
↑ Hartmanis, J.; Stearns, RE (1964). "Complejidad computacional de secuencias recursivas" (PDF) .
↑ Fortnow, Lance; Homer, Steve (2002). "Una breve historia de la complejidad computacional" (PDF) .
↑ Moore, Cristopher (31 de julio de 2019). "Autómatas, lenguajes y gramáticas". arXiv : 1907.12713 [ cs.CC ].
↑ Yan, Song Y. (1998). Introducción a los lenguajes formales y la computación automática . Singapur: World Scientific Publishing Co. Pte. Ltd. pp. 155–156 . ISBN 978-981-02-3422-5.
↑ Ferraguti, A.; Micheli, G.; Schnyder, R. (2018), Irreducible compositions of degree two polynomials over finite fields have regular structure , The Quarterly Journal of Mathematics, vol. 69, Oxford University Press, pp. 1089– 1099, arXiv : 1701.06040 , doi : 10.1093/qmath/hay015 , S2CID 3962424
↑ 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 .
↑ Jirí Adámek y Věra Trnková . 1990. Autómatas y Álgebras en Categorías . Editorial académica Kluwer: Dordrecht y Praga
↑ Mac Lane, Saunders (1971). Categorías para el matemático en activo . Nueva York: Springer. ISBN 978-0-387-90036-0.
↑ https://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.
↑ Aguiar, M. y Mahajan, S.2010. "Functores monoidales, especies y álgebras de Hopf" .
↑ Meseguer, J., Montanari, U.: 1990 Las redes de Petri son monoides. Information and Computation 88 :105–155

Lecturas adicionales

Hopcroft, John E .; Motwani, Rajeev ; Ullman, Jeffrey D. (2006) [1979]. Introducción a la teoría de autómatas, lenguajes y computación (3.ª ed.). Addison-Wesley. ISBN 0-321-45536-3.
Sipser, Michael (1997). Introducción a la teoría de la computación (1.ª ed.). PWS Publishing. ISBN 978-0-534-94728-6.( Accesible para usuarios con discapacidades visuales ) 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 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 . Serie de matemáticas de Chapman y Hall. Londres: Chapman & Hall . Zbl 0231.94041 .
John M. Howie (1991) Autómatas y lenguajes , Clarendon Press ISBN 0-19-853424-8MR 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. Zbl 1188.68177 .
James P. Schmeiser ; David T. Barnard (1995). Produciendo un orden de análisis sintáctico descendente con análisis sintáctico ascendente . Elsevier North-Holland.
Igor Aleksander ; 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

[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. Bibcode : 1967BiSys...1...95A . doi : 10.1016/0303-2647(67)90021-4 . PMID 6060865. Archivado del 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 sin ruido" (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.). Automata Studies . Princeton, NJ: Princeton University Press.

[Arbib_1969-5] 1 2 3 4 5 Arbib, Michael (1969). Teorías de autómatas abstractos . Englewood Cliffs, NJ: Prentice-Hall.

[6] Li, Ming; Paul, Vitanyi (1997). Una 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) del original el 7 de marzo de 2016.

[8] Nerode, A. (1958). "Transformaciones de autómatas lineales" . Actas de la Sociedad Matemática Americana . 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 del original el 14 de diciembre de 2010.

[structure_theory-10] 1 2 3 Hartmanis, J. ; Stearns, RE (1966). Teoría de la estructura algebraica de las 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 ].

[Aaniya_B-14] Yan, Song Y. (1998). Introducción a los lenguajes formales y la computación automática . Singapur: World Scientific Publishing Co. Pte. Ltd. pp. 155–156 . ISBN 978-981-02-3422-5.

[15] Ferraguti, A.; Micheli, G.; Schnyder, R. (2018), Irreducible compositions of degree two polynomials over finite fields have regular structure , The Quarterly Journal of Mathematics, vol. 69, Oxford University Press, pp. 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] ttps://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. Information and Computation 88 :105–155

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ] .

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]