Autómata finito determinista

Máquina de estados finitos

Un ejemplo de un autómata finito determinista que acepta sólo números binarios que son múltiplos de 3. El estado S ₀ es tanto el estado inicial como un estado de aceptación. Por ejemplo, la cadena "1001" conduce a la secuencia de estados S ₀ , S ₁ , S ₂ , S ₁ , S ₀ y, por tanto, se acepta.

En la teoría de la computación , una rama de la informática teórica , un autómata finito determinista ( DFA ), también conocido como aceptor finito determinista ( DFA ), máquina determinista de estados finitos ( DFSM ) o autómata determinista de estados finitos ( DFSA ), es una máquina de estados finitos que acepta o rechaza una determinada cadena de símbolos, ejecutando una secuencia de estados determinada únicamente por la cadena. ^[1] Determinista se refiere a la unicidad de la ejecución del cálculo. En busca de los modelos más simples para capturar máquinas de estados finitos, Warren McCulloch y Walter Pitts estuvieron entre los primeros investigadores en introducir un concepto similar al de autómatas finitos en 1943. ^{[2] [3]}

La figura ilustra un autómata finito determinista utilizando un diagrama de estados . En este autómata de ejemplo, hay tres estados: S ₀ , S ₁ y S ₂ (indicados gráficamente por círculos). El autómata toma una secuencia finita de 0 y 1 como entrada. Para cada estado, hay una flecha de transición que conduce al siguiente estado tanto para 0 como para 1. Al leer un símbolo, un DFA salta de manera determinista de un estado a otro siguiendo la flecha de transición. Por ejemplo, si el autómata se encuentra actualmente en el estado S ₀ y el símbolo de entrada actual es 1, entonces salta de manera determinista al estado S ₁ . Un DFA tiene un estado de inicio (indicado gráficamente por una flecha que surge de la nada) donde comienzan los cálculos y un conjunto de estados de aceptación (indicados gráficamente por un doble círculo) que ayudan a definir cuándo un cálculo es exitoso.

Un DFA se define como un concepto matemático abstracto, pero a menudo se implementa en hardware y software para resolver diversos problemas específicos, como el análisis léxico y la coincidencia de patrones . Por ejemplo, un DFA puede modelar un software que decide si las entradas de usuario en línea, como las direcciones de correo electrónico, son sintácticamente válidas. ^[4]

Los DFA se han generalizado a autómatas finitos no deterministas (NFA) que pueden tener varias flechas de la misma etiqueta a partir de un estado. Utilizando el método de construcción powerset , cada NFA se puede traducir a un DFA que reconozca el mismo idioma. Los DFA, y también los NFA, reconocen exactamente el conjunto de lenguajes regulares . ^[1]

Definicion formal

Un autómata finito determinista M es una tupla de 5 , ( Q , Σ, δ , q ₀ , F ) , que consta de

• un conjunto finito de estados Q
• un conjunto finito de símbolos de entrada llamado alfabeto Σ
• una función de transición δ  : Q × Σ → Q
• un estado inicial o de inicio ${\displaystyle q_{0}\in Q}$
• un conjunto de estados de aceptación ${\displaystyle F\subseteq Q}$

Sea w = a ₁ a ₂ ... a _n una cadena sobre el alfabeto Σ . El autómata M acepta la cadena w si existe una secuencia de estados, r ₀ , r ₁ , ..., r _n , en Q con las siguientes condiciones:

1. r ₀ = q ₀
2. r _{i +1} = δ ( r _i , a _{i +1} ) , para i = 0, ..., n − 1
3. ${\displaystyle r_{n}\in F}$.

En palabras, la primera condición dice que la máquina arranca en el estado inicial q ₀ . La segunda condición dice que dado cada carácter de la cadena w , la máquina pasará de un estado a otro de acuerdo con la función de transición δ . La última condición dice que la máquina acepta w si la última entrada de w hace que la máquina se detenga en uno de los estados de aceptación. En caso contrario, se dice que el autómata rechaza la cuerda. El conjunto de cadenas que M acepta es el lenguaje reconocido por M y este lenguaje se denota por L ( M ) .

Un autómata finito determinista sin estados de aceptación y sin estado inicial se conoce como sistema de transición o semiautómata .

Para una introducción más completa de la definición formal, consulte teoría de autómatas .

Ejemplo

El siguiente ejemplo es de un DFAM , con un alfabeto binario, que requiere que la entrada contenga un número par de ceros.

El diagrama de estado para M

M = ( Q , Σ, δ , q ₀ , F ) donde

• Q = { S ₁ , S ₂ }
• Σ = {0, 1}
• q ₀ = S ₁
• F = { S ₁ } y
• δ se define mediante la siguiente tabla de transición de estados :

El estado S ₁ representa que ha habido un número par de ceros en la entrada hasta el momento, mientras que S ₂ significa un número impar. Un 1 en la entrada no cambia el estado del autómata. Cuando finalice la entrada, el estado mostrará si la entrada contenía un número par de ceros o no. Si la entrada contenía un número par de ceros, M terminará en el estado S ₁ , un estado de aceptación, por lo que la cadena de entrada será aceptada.

El lenguaje reconocido por M es el lenguaje regular dado por la expresión regular (1*) (0 (1*) 0 (1*))* , donde *la estrella de Kleene , por ejemplo, 1*denota cualquier número (posiblemente cero) de unos consecutivos.

Variaciones

Completo e incompleto

Según la definición anterior, los autómatas finitos deterministas son siempre completos : definen a partir de cada estado una transición para cada símbolo de entrada.

Si bien esta es la definición más común, algunos autores utilizan el término autómata finito determinista para una noción ligeramente diferente: un autómata que define como máximo una transición para cada estado y cada símbolo de entrada; se permite que la función de transición sea parcial . ^[5] Cuando no se define ninguna transición, dicho autómata se detiene.

autómatas locales

Un autómata local es un DFA, no necesariamente completo, en el que todas las aristas con la misma etiqueta conducen a un único vértice. Los autómatas locales aceptan la clase de idiomas locales , aquellos para los cuales la pertenencia de una palabra al idioma está determinada por una "ventana deslizante" de longitud dos en la palabra. ^{[6] [7]}

Un gráfico Myhill sobre un alfabeto A es un gráfico dirigido con un conjunto de vértices A y subconjuntos de vértices etiquetados como "inicio" y "final". El lenguaje aceptado por un gráfico Myhill es el conjunto de caminos dirigidos desde un vértice inicial hasta un vértice final: el gráfico actúa así como un autómata. ^[6] La clase de idiomas aceptada por los gráficos Myhill es la clase de idiomas locales. ^[8]

Aleatoriedad

Cuando se ignoran el estado inicial y los estados de aceptación, un DFA de n estados y un alfabeto de tamaño k se puede ver como un dígrafo de n vértices en el que todos los vértices tienen k arcos exteriores etiquetados 1, ..., k (a k -dígrafo de salida). Se sabe que cuando k ≥ 2 es un entero fijo, con alta probabilidad, el componente fuertemente conectado (SCC) más grande en tal dígrafo k -out elegido uniformemente al azar es de tamaño lineal y puede ser alcanzado por todos los vértices. ^[9] También se ha demostrado que si se permite que k aumente a medida que aumenta n , entonces todo el dígrafo tiene una transición de fase para una conectividad fuerte similar al modelo de conectividad de Erdős-Rényi . ^[10]

En un DFA aleatorio, el número máximo de vértices alcanzables desde un vértice es muy cercano al número de vértices en el SCC más grande con alta probabilidad. ^{[9] [11]} Esto también es cierto para el subdígrafo inducido más grande de grado uno mínimo, que puede verse como una versión dirigida de 1 -core . ^[10]

Propiedades de cierre

El autómata superior izquierdo reconoce el idioma de todas las cadenas binarias que contienen al menos una aparición de "00". El autómata inferior derecho reconoce todas las cadenas binarias con un número par de "1". El autómata inferior izquierdo se obtiene como producto de los dos anteriores, reconoce la intersección de ambos lenguajes.

Si los DFA reconocen los idiomas que se obtienen al aplicar una operación en los idiomas reconocibles del DFA, se dice que los DFA están cerrados bajo la operación. Los DFA se cierran mediante las siguientes operaciones.

• Unión
• Intersección ^{[12] : 59–60} (ver imagen)
• Concatenación
• Complementar
• cierre kleene
• Inversión
• Cociente ^{[ cita necesaria ]}
• Sustitución ^{[ cita necesaria ]}
• Homomorfismo ^{[ cita necesaria ]}

Para cada operación, se ha determinado una construcción óptima con respecto al número de estados en la investigación de complejidad estatal . Dado que los DFA son equivalentes a autómatas finitos no deterministas (NFA), estos cierres también se pueden probar utilizando las propiedades de cierre de los NFA.

Como monoide de transición

Una ejecución de un DFA determinado puede verse como una secuencia de composiciones de una formulación muy general de la función de transición consigo misma. Aquí construimos esa función.

Para un símbolo de entrada dado , se puede construir una función de transición definiendo para todos . (Este truco se llama curry .) Desde esta perspectiva, "actúa" sobre un estado en Q para producir otro estado. Entonces se puede considerar el resultado de la composición de funciones aplicada repetidamente a las distintas funciones , , etc. Dado un par de letras , se puede definir una nueva función , donde denota la composición de la función. ${\displaystyle a\in \Sigma }$ ${\displaystyle \delta _{a}:Q\rightarrow Q}$ ${\displaystyle \delta _{a}(q)=\delta (q,a)}$ ${\displaystyle q\in Q}$ ${\displaystyle \delta _{a}}$ ${\displaystyle \delta _{a}}$ ${\displaystyle \delta _{b}}$ ${\displaystyle a,b\in \Sigma }$ ${\displaystyle {\widehat {\delta }}_{ab}=\delta _{a}\circ \delta _{b}}$ ${\displaystyle \circ }$

Claramente, este proceso puede continuarse recursivamente, dando la siguiente definición recursiva de : ${\displaystyle {\widehat {\delta }}:Q\times \Sigma ^{\star }\rightarrow Q}$

${\displaystyle {\widehat {\delta }}(q,\epsilon )=q}$, donde está la cadena vacía y ${\displaystyle \epsilon }$

${\displaystyle {\widehat {\delta }}(q,wa)=\delta _{a}({\widehat {\delta }}(q,w))}$, dónde y . ${\displaystyle w\in \Sigma ^{*},a\in \Sigma }$ ${\displaystyle q\in Q}$

${\displaystyle {\widehat {\delta }}}$ está definido para todas las palabras . Una ejecución del DFA es una secuencia de composiciones consigo mismo. ${\displaystyle w\in \Sigma ^{*}}$ ${\displaystyle {\widehat {\delta }}}$

La composición de funciones repetidas forma un monoide . Para las funciones de transición, este monoide se conoce como monoide de transición o, a veces, semigrupo de transformación . La construcción también se puede invertir: dado a , se puede reconstruir a , por lo que las dos descripciones son equivalentes. ${\displaystyle {\widehat {\delta }}}$ ${\displaystyle \delta }$

Ventajas y desventajas

Los DFA son uno de los modelos de cálculo más prácticos, ya que existe un algoritmo en línea trivial de tiempo lineal y espacio constante para simular un DFA en un flujo de entrada. Además, existen algoritmos eficientes para encontrar un DFA que reconozca:

• el complemento del idioma reconocido por un DFA determinado.
• la unión/intersección de las lenguas reconocidas por dos DFA determinados.

Debido a que los DFA se pueden reducir a una forma canónica ( DFA mínimos ), también existen algoritmos eficientes para determinar:

• si un DFA acepta cadenas (problema de vacío)
• si un DFA acepta todas las cadenas (problema de universalidad)
• si dos DFA reconocen el mismo idioma (problema de igualdad)
• si el idioma reconocido por un DFA está incluido en el idioma reconocido por un segundo DFA (Problema de inclusión)
• el DFA con un número mínimo de estados para un idioma regular particular (Problema de minimización)

Los DFA son equivalentes en potencia de cálculo a los autómatas finitos no deterministas (NFA). Esto se debe, en primer lugar, a que cualquier DFA también es una NFA, por lo que una NFA puede hacer lo que una DFA puede hacer. Además, dada una NFA, utilizando la construcción powerset se puede construir una DFA que reconozca el mismo lenguaje que la NFA, aunque la DFA podría tener un número exponencialmente mayor de estados que la NFA. ^{[13] [14]} Sin embargo, aunque las NFA son computacionalmente equivalentes a las DFA, los problemas mencionados anteriormente no necesariamente se resuelven de manera eficiente también para las NFA. El problema de no universalidad para las NFA es el PSPACE completo , ya que hay NFA pequeñas con la palabra de rechazo más corta en tamaño exponencial. Un AFD es universal si y sólo si todos los estados son estados finales, pero esto no es válido para los AFN. Los Problemas de Igualdad, Inclusión y Minimización también son PSPACE completos ya que requieren formar el complemento de una NFA lo que resulta en una explosión exponencial de tamaño. ^[15]

Por otro lado, los autómatas de estados finitos tienen un poder estrictamente limitado en los lenguajes que pueden reconocer; Un DFA no puede reconocer muchos lenguajes simples, incluido cualquier problema que requiera más que un espacio constante para resolverse. El ejemplo clásico de un lenguaje descrito de forma sencilla que ningún DFA puede reconocer es el lenguaje entre paréntesis o Dyck , es decir, el lenguaje que consta de paréntesis correctamente emparejados, como la palabra "(()())". Intuitivamente, ningún DFA puede reconocer el lenguaje Dyck porque los DFA no son capaces de contar: un autómata tipo DFA necesita tener un estado para representar cualquier número posible de paréntesis "actualmente abiertos", lo que significa que necesitaría un número ilimitado de estados. Otro ejemplo más simple es el lenguaje que consiste en cadenas de la forma a ⁿ b ⁿ para algún número finito pero arbitrario de a ' s, seguido de un número igual de b ' s. ^[dieciséis]

Identificación de DFA a partir de palabras etiquetadas

Dado un conjunto de palabras positivas y un conjunto de palabras negativas , se puede construir un DFA que acepte todas las palabras y rechace todas las palabras de : este problema se llama identificación DFA (síntesis, aprendizaje). Si bien algunos DFA se pueden construir en tiempo lineal, el problema de identificar un DFA con el número mínimo de estados es NP-completo. ^[17] Trakhtenbrot y Barzdin propusieron el primer algoritmo para la identificación mínima de DFA ^[18] y se denomina algoritmo TB . Sin embargo, el algoritmo TB supone que todas las palabras hasta una longitud determinada están contenidas en cualquiera de los dos . ${\displaystyle S^{+}\subset \Sigma ^{*}}$ ${\displaystyle S^{-}\subset \Sigma ^{*}}$ ${\displaystyle S^{+}}$ ${\displaystyle S^{-}}$ ${\displaystyle \Sigma }$ ${\displaystyle S^{+}\cup S^{-}}$

Más tarde, K. Lang propuso una extensión del algoritmo TB que no utiliza ninguna suposición sobre y , el algoritmo Traxbar . ^[19] Sin embargo, Traxbar no garantiza la minimalidad del DFA construido. En su trabajo ^[17] EM Gold también propuso un algoritmo heurístico para una identificación mínima de DFA. El algoritmo de Gold supone que contiene un conjunto de características del lenguaje regular; de lo contrario, el DFA construido será inconsistente con o . Otros algoritmos de identificación DFA notables incluyen el algoritmo RPNI, ^[20] el algoritmo de fusión de estados basado en evidencia Blue-Fringe, ^[21] y Windowed-EDSM. ^[22] Otra dirección de investigación es la aplicación de algoritmos evolutivos : el algoritmo evolutivo de etiquetado de estados inteligentes ^[23] permitió resolver un problema de identificación DFA modificado en el que los datos de entrenamiento (conjuntos y ) son ruidosos en el sentido de que algunas palabras se atribuyen a clases equivocadas. ${\displaystyle S^{+}}$ ${\displaystyle S^{-}}$ ${\displaystyle S^{+}}$ ${\displaystyle S^{-}}$ ${\displaystyle S^{+}}$ ${\displaystyle S^{-}}$ ${\displaystyle S^{+}}$ ${\displaystyle S^{-}}$

Un paso más se debe a la aplicación de los solucionadores SAT por parte de Marjin JH Heule y S. Verwer: el problema mínimo de identificación de DFA se reduce a decidir la satisfacibilidad de una fórmula booleana. ^[24] La idea principal es construir un aceptador de árbol de prefijos aumentado (un trie que contiene todas las palabras de entrada con las etiquetas correspondientes) basado en los conjuntos de entrada y reducir el problema de encontrar un DFA con estados para colorear los vértices del árbol con estados en tales de una manera que cuando los vértices con un color se fusionan en un estado, el autómata generado es determinista y cumple con y . Aunque este enfoque permite encontrar el DFA mínimo, sufre un aumento exponencial del tiempo de ejecución cuando aumenta el tamaño de los datos de entrada. Por lo tanto, el algoritmo inicial de Heule y Verwer se ha ampliado posteriormente realizando varios pasos del algoritmo EDSM antes de la ejecución del solucionador SAT: el algoritmo DFASAT. ^[25] Esto permite reducir el espacio de búsqueda del problema, pero conduce a la pérdida de la garantía de minimalidad. Ulyantsev et al. han propuesto otra forma de reducir el espacio de búsqueda. ^[26] mediante nuevos predicados de ruptura de simetría basados ​​en el algoritmo de búsqueda en amplitud : los estados de DFA buscados están obligados a numerarse de acuerdo con el algoritmo BFS lanzado desde el estado inicial. Este enfoque reduce el espacio de búsqueda al eliminar los autómatas isomórficos. ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle S^{+}}$ ${\displaystyle S^{-}}$ ${\displaystyle C!}$

Modelos equivalentes

Máquinas de Turing de solo lectura con movimiento hacia la derecha

Las máquinas de Turing de solo lectura que se mueven hacia la derecha son un tipo particular de máquina de Turing que solo se mueve hacia la derecha; estos son casi exactamente equivalentes a los DFA. ^[27] La ​​definición basada en una cinta individualmente infinita es una tupla de 7

${\displaystyle M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},F\rangle ,}$

dónde

${\displaystyle Q}$es un conjunto finito de estados ;

${\displaystyle \Gamma }$es un conjunto finito de alfabetos/símbolos de cinta ;

${\displaystyle b\in \Gamma }$es el símbolo en blanco (el único símbolo que se permite que aparezca en la cinta con infinitas veces en cualquier paso durante el cálculo);

${\displaystyle \Sigma }$, un subconjunto de no incluir b , es el conjunto de símbolos de entrada ; ${\displaystyle \Gamma }$

${\displaystyle \delta :Q\times \Gamma \to Q\times \Gamma \times \{R\}}$es una función llamada función de transición , R es un movimiento hacia la derecha (un desplazamiento hacia la derecha);

${\displaystyle q_{0}\in Q}$es el estado inicial ;

${\displaystyle F\subseteq Q}$es el conjunto de estados finales o aceptantes .

La máquina siempre acepta un idioma regular. Debe existir al menos un elemento del conjunto F (un estado HALT ) para que el idioma no esté vacío.

Ejemplo de una máquina de Turing de solo lectura de 3 estados y 2 símbolos

${\displaystyle Q=\{A,B,C,{\text{HALT}}\};}$

${\displaystyle \Gamma =\{0,1\};}$

${\displaystyle b=0}$, "blanco";

${\displaystyle \Sigma =\varnothing }$, conjunto vacio;

${\displaystyle \delta =}$ver tabla de estado arriba;

${\displaystyle q_{0}=A}$, estado inicial;

${\displaystyle F=}$el conjunto de un elemento de estados finales: . ${\displaystyle \{{\text{HALT}}\}}$

Ver también

• Autómata determinista de estado finito acíclico
• Minimización de DFA
• Lógica monádica de segundo orden
• Construcción del conjunto de potencia
• Autómata cuántico finito
• problema de separar palabras
• máquina de Turing
• Autómata finito de dos vías
• autómata ponderado

Notas

1. Hopcroft 2001
2. McCulloch y Pitts (1943)
3. Rabin y Scott (1959)
4. Gouda, Prabhakar, Aplicación de autómatas finitos
5. Mogensen, Torben Aegidius (2011). "Análisis léxico". Introducción al diseño de compiladores . Temas de Pregrado en Ciencias de la Computación. Londres: Springer. pag. 12. doi :10.1007/978-0-85729-829-4_1. ISBN 978-0-85729-828-7.
6. Lawson (2004) p.129
7. Sakarovich (2009) p.228
8. Lawson (2004) p.128
9. Grusho, AA (1973). "Limitar distribuciones de determinadas características de gráficos de autómatas aleatorios". Apuntes Matemáticos de la Academia de Ciencias de la URSS . 4 : 633–637. doi :10.1007/BF01095785. S2CID  121723743.
10. Cai, Xing Shi; Devroye, Luc (octubre de 2017). "La estructura gráfica de un autómata determinista elegido al azar". Algoritmos y estructuras aleatorias . 51 (3): 428–458. arXiv : 1504.06238 . doi :10.1002/rsa.20707. S2CID  13013344.
11. Carayol, Arnaud; Nicaud, Cyril (febrero de 2012). Distribución del número de estados accesibles en un autómata determinista aleatorio. STACS'12 (29º Simposio sobre Aspectos Teóricos de la Informática). vol. 14. París, Francia. págs. 194-205.
12. John E. Hopcroft y Jeffrey D. Ullman (1979). Introducción a la teoría, los lenguajes y la computación de autómatas . Lectura/MA: Addison-Wesley. ISBN 0-201-02988-X.
13. Sakarovitch (2009) p.105
14. Lawson (2004) p.63
15. Esparza Estaún, Francisco Javier; Sickert, Salomón; Blondin, Michael (16 de noviembre de 2016). «Operaciones y pruebas sobre decorados: Implementación sobre DFA» (PDF) . Autómatas y Lenguajes Formales 2017/18 . Archivado desde el original (PDF) el 8 de agosto de 2018.
16. Lawson (2004) p.46
17. Oro, EM (1978). "Complejidad de la identificación de autómatas a partir de datos determinados". Información y Control . 37 (3): 302–320. doi :10.1016/S0019-9958(78)90562-4.
18. De Vries, A. (28 de junio de 2014). Autómatas finitos: comportamiento y síntesis. Elsevier. ISBN 9781483297293.
19. Lang, Kevin J. (1992). "Los DFA aleatorios se pueden aprender aproximadamente a partir de escasos ejemplos uniformes". Actas del quinto taller anual sobre teoría del aprendizaje computacional: COLT '92 . págs. 45–52. doi :10.1145/130385.130390. ISBN 089791497X. S2CID  7480497.
20. Oncina, J.; García, P. (1992). "Inferir lenguajes regulares en tiempo de actualización polinomial". Reconocimiento de patrones y análisis de imágenes . Serie sobre Percepción de Máquinas e Inteligencia Artificial. vol. 1. págs. 49–61. doi :10.1142/9789812797902_0004. ISBN 978-981-02-0881-3.
21. Lang, Kevin J.; Pearlmutter, Barak A.; Precio, Rodney A. (1998). "Resultados del concurso de aprendizaje Abbadingo one DFA y un nuevo algoritmo de fusión de estados basado en evidencia". Inferencia gramatical (PDF) . Apuntes de conferencias sobre informática. vol. 1433, págs. 1-12. doi :10.1007/BFb0054059. ISBN 978-3-540-64776-8.
22. Más allá de EDSM | Actas del VI Coloquio Internacional sobre Inferencia Gramatical: Algoritmos y Aplicaciones. 23 de septiembre de 2002. págs. 37–48. ISBN 9783540442394.
23. Lucas, SM; Reynolds, TJ (2005). "Aprendizaje de autómatas finitos deterministas con un algoritmo evolutivo de etiquetado de estado inteligente". Transacciones IEEE sobre análisis de patrones e inteligencia artificial . 27 (7): 1063–1074. doi :10.1109/TPAMI.2005.143. PMID  16013754. S2CID  14062047.
24. Heule, MJH (2010). "Identificación exacta de DFA mediante solucionadores SAT". Inferencia gramatical: resultados teóricos y aplicaciones . Inferencia gramatical: resultados teóricos y aplicaciones. ICGI 2010. Apuntes de conferencias sobre informática. Apuntes de conferencias sobre informática. vol. 6339, págs. 66–79. doi :10.1007/978-3-642-15488-1_7. ISBN 978-3-642-15487-4.
25. Heule, Marijn JH ; Verwer, Sicco (2013). "Síntesis de modelos de software mediante solucionadores de satisfacibilidad". Ingeniería de software empírica . 18 (4): 825–856. doi :10.1007/s10664-012-9222-z. hdl : 2066/103766 . S2CID  17865020.
26. Ulyantsev, Vladimir; Zakirzyanov, Ilya; Shalyto, Anatoly (2015). "Predicados de ruptura de simetría basados ​​en BFS para la identificación de DFA". Teoría y aplicaciones del lenguaje y los autómatas . Apuntes de conferencias sobre informática. vol. 8977, págs. 611–622. doi :10.1007/978-3-319-15579-1_48. ISBN 978-3-319-15578-4.
27. Davis, Martín; Ron Sigal; Elaine J. Weyuker (1994). Segunda edición: Computabilidad, complejidad y lenguajes y lógica: fundamentos de la informática teórica (2ª ed.). San Diego: Prensa académica, Harcourt, Brace & Company. ISBN 0-12-206382-1.

Referencias

• Hopcroft, John E .; Motwani, Rajeev ; Ullman, Jeffrey D. (2001). Introducción a la teoría, los lenguajes y la computación de los autómatas (2 ed.). Boston: Addison Wesley . ISBN 0-201-44124-1.
• Lawson, Mark V. (2004). Autómatas finitos . Chapman y Hall/CRC. ISBN 1-58488-255-7. Zbl  1086.68074.
• McCulloch, WS; Pitts, W. (1943). "Un cálculo lógico de las ideas inmanentes a la actividad nerviosa". Boletín de Biofísica Matemática . 5 (4): 115-133. doi :10.1007/BF02478259. PMID  2185863.
• Rabin, MO; Scott, D. (1959). "Autómatas finitos y sus problemas de decisión". IBM J. Res. Desarrollo . 3 (2): 114-125. doi :10.1147/rd.32.0114.
• Sakarovich, Jacques (2009). Elementos de la teoría de los autómatas . Traducido del francés por Reuben Thomas. Cambridge: Prensa de la Universidad de Cambridge . ISBN 978-0-521-84425-3. Zbl  1188.68177.
• Sipser, Michael (1997). Introducción a la Teoría de la Computación . Boston: PWS. ISBN 0-534-94728-X.. Sección 1.1: Autómatas finitos, págs. 31–47. Subsección "Problemas decidibles relacionados con los lenguajes habituales" de la sección 4.1: Idiomas decidibles, págs. 152 a 155.4.4 DFA solo puede aceptar lenguaje regular