Hispanopedia Wiki
Articulo de referencia

Autómata finito determinista

Un ejemplo de autómata finito determinista que solo acepta números binarios múltiplos de 3. El estado S₀ es tanto el estado inicial como un estado de aceptación. Por ejemplo, la...

Hispanopedia WikiContenido en espanolLectura gratuita

Un ejemplo de autómata finito determinista que solo acepta números binarios 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 lo tanto, es aceptada.

En la teoría de la computación , una rama de la informática teórica , un autómata finito determinista ( AFD ) —también conocido como aceptador finito determinista ( AFD ), máquina de estados finitos determinista ( MEFD ) o autómata de estados finitos determinista ( AEFD )— es una máquina de estados finitos que acepta o rechaza una cadena de símbolos dada, recorriendo una secuencia de estados determinada de forma única por la cadena. [ 1 ] Determinista se refiere a la unicidad de la ejecución de la computación. En busca de los modelos más simples para representar máquinas de estados finitos, Warren McCulloch y Walter Pitts fueron de 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 mediante un diagrama de estados . En este ejemplo, existen tres estados: S₀ , S₁ y S₂ ( representados gráficamente por círculos). El autómata recibe como entrada una secuencia finita de 0 y 1. Para cada estado, existe una flecha de transición que conduce al siguiente estado, tanto para 0 como para 1. Al leer un símbolo, el autómata finito determinista salta de un estado a otro siguiendo la flecha de transición. Por ejemplo, si el autómata se encuentra en el estado S₀ y el símbolo de entrada actual es 1, salta deterministamente al estado S₁ . Un autómata finito determinista tiene un estado inicial (representado gráficamente por una flecha que aparece desde ningún lugar) donde comienzan los cálculos, y un conjunto de estados de aceptación (representados gráficamente por un doble círculo) que ayudan a definir cuándo un cálculo es exitoso.

Un autómata finito determinista (AFD) 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 AFD puede modelar software que decide si la entrada de usuario en línea, como las direcciones de correo electrónico, es sintácticamente válida. [ 4 ]

Los autómatas finitos deterministas ( AFD) se han generalizado a autómatas finitos no deterministas (AFN) , que pueden tener varias flechas de la misma etiqueta que parten de un estado. Mediante el método de construcción de conjuntos potencia , todo AFN puede traducirse a un AFD que reconoce el mismo lenguaje. Tanto los AFD como los AFN reconocen exactamente el conjunto de lenguajes regulares . [ 1 ]

Definición formal

Un autómata finito determinista M es una 5- tupla , ( Q , Σ, δ , q 0 , 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 partida)q0∈Q{\displaystyle q_{0}\in Q}
  • un conjunto de estados de aceptación (o finales)F⊆Q{\displaystyle F\subseteq Q}

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

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

En otras palabras, la primera condición indica que la máquina comienza en el estado inicial q₀ . La segunda condición indica que, dado cada carácter de la cadena w , la máquina transitará de un estado a otro según la función de transición δ . La última condición indica que la máquina acepta w si la última entrada de w provoca 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 cadena. 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 un 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 la teoría de autómatas .

Ejemplo

El siguiente ejemplo corresponde a un autómata finito determinista (AFD) M , con un alfabeto binario, que requiere que la entrada contenga un número par de ceros.

El diagrama de estados para M

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

El estado S1 indica que la entrada ha tenido un número par de ceros hasta el momento, mientras que S2 indica un número impar. Un 1 en la entrada no altera el estado del autómata. Al finalizar la entrada, el estado mostrará si esta contenía un número par de ceros o no. Si la entrada contenía un número par de ceros, M finalizará en el estado S1 , 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 *es 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 desde cada estado una transición para cada símbolo de entrada.

Aunque 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; la función de transición puede ser parcial . [ 5 ] Cuando no se define ninguna transición, dicho autómata se detiene.

Autómatas locales

Un autómata local es un autómata finito determinista (AFD), 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 lenguajes locales , aquellos en los que la pertenencia de una palabra al lenguaje se determina mediante una "ventana deslizante" de longitud dos sobre la palabra. [ 6 ] [ 7 ]

Un grafo de Myhill sobre un alfabeto A es un grafo dirigido con un conjunto de vértices A y subconjuntos de vértices etiquetados como "inicio" y "fin". El lenguaje aceptado por un grafo de Myhill es el conjunto de caminos dirigidos desde un vértice de inicio hasta un vértice de fin: el grafo actúa así como un autómata. [ 6 ] La clase de lenguajes aceptados por los grafos de Myhill es la clase de lenguajes locales. [ 8 ]

Aleatoriedad

Cuando se ignoran los estados inicial y de aceptación, un DFA de n estados y un alfabeto de tamaño k puede verse como un digrafo de n vértices en el que todos los vértices tienen k arcos de salida etiquetados del 1 al k (un digrafo de k salidas). Se sabe que cuando k ≥ 2 es un entero fijo, con alta probabilidad, el componente fuertemente conexo (SCC) más grande en dicho digrafo de k salidas, 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 n aumenta, entonces todo el digrafo tiene una transición de fase para la conectividad fuerte similar al modelo de Erdős-Rényi para la conectividad. [ 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 subdigrafo inducido más grande de grado de entrada mínimo uno, que puede verse como una versión dirigida de 1 -core . [ 10 ]

Propiedades de cierre

El autómata superior izquierdo reconoce el lenguaje 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 y reconoce la intersección de ambos lenguajes.

Si los autómatas finitos deterministas (AFD) reconocen los lenguajes que se obtienen al aplicar una operación sobre los lenguajes reconocibles por los AFD, entonces se dice que los AFD son cerrados bajo dicha operación. Los AFD son cerrados bajo las siguientes operaciones.

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

Como monoide de transición

Una ejecución de un autómata finito determinista (AFD) dado 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 dadoa∈Σ{\displaystyle a\in \Sigma }, se puede construir una función de transiciónδa:Q→Q{\displaystyle \delta _{a}:Q\rightarrow Q}definiendoδa(q)=δ(q,a){\displaystyle \delta _ {a}(q)=\delta (q,a)}a pesar deq∈Q{\displaystyle q\in Q}. (Este truco se llama currying .) Desde esta perspectiva,δa{\displaystyle \delta _{a}}"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 diversas funciones.δa{\displaystyle \delta _{a}},δb{\displaystyle \delta _{b}}y así sucesivamente. Dado un par de letrasa,b∈Σ{\displaystyle a,b\in \Sigma }, se puede definir una nueva funciónδ^ab=δa∘δb{\displaystyle {\widehat {\delta }}_{ab}=\delta _{a}\circ \delta _{b}}, dónde∘{\displaystyle \circ }denota composición de funciones.

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

δ^(q,ϵ)=q{\displaystyle {\widehat {\delta }}(q,\epsilon )=q}, dóndeϵ{\displaystyle \epsilon }es la cadena vacía y
δ^(q,wa)=δa(δ^(q,w)){\displaystyle {\widehat {\delta }}(q,wa)=\delta _{a}({\widehat {\delta }}(q,w))}, dóndew∈Σ∗,a∈Σ{\displaystyle w\in \Sigma ^{*},a\in \Sigma }yq∈Q{\displaystyle q\in Q}.

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

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 puede invertirse: dado unδ^{\displaystyle {\widehat {\delta }}}, se puede reconstruir unδ{\displaystyle \delta }y, por lo tanto, las dos descripciones son equivalentes.

Ventajas y desventajas

Los autómatas finitos deterministas (AFD) son uno de los modelos de computación más prácticos, ya que existe un algoritmo en línea trivial, de tiempo lineal y espacio constante para simular un AFD en un flujo de entrada. Además, existen algoritmos eficientes para encontrar un AFD que reconozca:

  • el complemento del lenguaje reconocido por un autómata finito determinista (AFD) dado.
  • la unión/intersección de los lenguajes reconocidos por dos autómatas finitos deterministas (AFD) dados.

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 autómata finito determinista (AFD) acepta cualquier cadena (problema de vacuidad).
  • Si un autómata finito determinista (AFD) acepta todas las cadenas (problema de universalidad).
  • Si dos autómatas finitos deterministas (AFD) reconocen el mismo idioma (Problema de igualdad)
  • Si el lenguaje reconocido por un autómata finito determinista (AFD) está incluido en el lenguaje reconocido por un segundo AFD (Problema de Inclusión).
  • El autómata finito determinista (AFD) con un número mínimo de estados para un lenguaje regular particular (Problema de minimización).

Los autómatas finitos deterministas ( AFD) son equivalentes en potencia computacional a los autómatas finitos no deterministas (AFN). Esto se debe a que, en primer lugar, cualquier AFD es también un AFN, por lo que un AFN puede hacer lo que un AFD puede hacer. Además, dado un AFN, utilizando la construcción de conjuntos potencia , se puede construir un AFD que reconozca el mismo lenguaje que el AFN, aunque el AFD podría tener un número de estados exponencialmente mayor que el AFN. [ 15 ] [ 16 ] Sin embargo, aunque los AFN son computacionalmente equivalentes a los AFD, los problemas mencionados anteriormente no necesariamente se resuelven de manera eficiente también para los AFN. El problema de la no universalidad para los AFN es PSPACE completo, ya que hay AFN pequeños con la palabra de rechazo más corta en tamaño exponencial. Un AFD es universal si y solo si todos los estados son estados finales, pero esto no se cumple para los AFN. Los problemas de igualdad, inclusión y minimización también son PSPACE completos, ya que requieren formar el complemento de un AFN, lo que resulta en una explosión exponencial de tamaño. [ 17 ]

Por otro lado, los autómatas de estados finitos tienen una capacidad estrictamente limitada en los lenguajes que pueden reconocer; muchos lenguajes simples, incluyendo cualquier problema que requiera más que un espacio constante para resolverse, no pueden ser reconocidos por un autómata finito determinista (AFD). El ejemplo clásico de un lenguaje descrito de forma simple que ningún AFD puede reconocer es el lenguaje de corchetes o lenguaje de Dyck , es decir, el lenguaje que consiste en corchetes correctamente emparejados como la palabra "(()())". Intuitivamente, ningún AFD puede reconocer el lenguaje de Dyck porque los AFD no son capaces de contar: un autómata similar a un AFD 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 n b n para algún número finito pero arbitrario de a 's , seguido de un número igual de b 's . [ 18 ]

Identificación DFA a partir de palabras etiquetadas

Dado un conjunto de palabras positivasS+⊂Σ∗{\displaystyle S^{+}\subset \Sigma ^{*}}y un conjunto de palabras negativasS−⊂Σ∗{\displaystyle S^{-}\subset \Sigma ^{*}}uno puede construir un DFA que acepte todas las palabras deS+{\displaystyle S^{+}}y rechaza todas las palabras deS−{\displaystyle S^{-}}Este problema se denomina identificación de DFA (síntesis, aprendizaje). Si bien algunos DFA pueden construirse en tiempo lineal, el problema de identificar un DFA con el número mínimo de estados es NP-completo. [ 19 ] El primer algoritmo para la identificación mínima de DFA fue propuesto por Trakhtenbrot y Barzdin [ 20 ] y se denomina algoritmo TB . Sin embargo, el algoritmo TB asume que todas las palabras deΣ{\displaystyle \Sigma }hasta una longitud determinada están contenidos en cualquiera de los dosS+∪S−{\displaystyle S^{+}\cup S^{-}}.

Más tarde, K. Lang propuso una extensión del algoritmo TB que no utiliza ninguna suposición sobreS+{\displaystyle S^{+}}yS−{\displaystyle S^{-}}, el algoritmo Traxbar . [ 21 ] Sin embargo, Traxbar no garantiza la minimalidad del DFA construido. En su trabajo [ 19 ] EM Gold también propuso un algoritmo heurístico para la identificación de DFA mínimos. El algoritmo de Gold supone queS+{\displaystyle S^{+}}yS−{\displaystyle S^{-}}contener un conjunto característico del lenguaje regular; de lo contrario, el DFA construido será inconsistente conS+{\displaystyle S^{+}}oS−{\displaystyle S^{-}}Otros algoritmos de identificación DFA notables incluyen el algoritmo RPNI, [ 22 ] el algoritmo de fusión de estados impulsado por evidencia Blue-Fringe, [ 23 ] y Windowed-EDSM. [ 24 ] Otra dirección de investigación es la aplicación de algoritmos evolutivos : el algoritmo evolutivo de etiquetado de estado inteligente [ 25 ] permitió resolver un problema de identificación DFA modificado en el que los datos de entrenamiento (conjuntosS+{\displaystyle S^{+}}yS−{\displaystyle S^{-}}) es ruidoso en el sentido de que algunas palabras se atribuyen a clases incorrectas.

Otro paso adelante se debe a la aplicación de solucionadores SAT por 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. [ 26 ] La idea principal es construir un aceptador de árbol de prefijos aumentado (un trie que contiene todas las palabras de entrada con etiquetas correspondientes) basado en los conjuntos de entrada y reducir el problema de encontrar un DFA condo{\displaystyle C}estados para colorear los vértices del árbol condo{\displaystyle C}estados de tal manera que cuando los vértices con un color se fusionan en un estado, el autómata generado es determinista y cumple conS+{\displaystyle S^{+}}yS−{\displaystyle S^{-}}Aunque este enfoque permite encontrar el DFA mínimo, sufre de 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. [ 27 ] Esto permite reducir el espacio de búsqueda del problema, pero conlleva la pérdida de la garantía de minimalidad. Ulyantsev et al. [ 28 ] propusieron otra forma de reducir el espacio de búsqueda mediante nuevos predicados de ruptura de simetría basados ​​en el algoritmo de búsqueda en anchura : los estados del DFA buscado se restringen a ser numerados de acuerdo con el algoritmo BFS lanzado desde el estado inicial. Este enfoque reduce el espacio de búsqueda endo¡{\displaystyle C!}eliminando los autómatas isomorfos.

Modelos equivalentes

Máquinas de Turing de solo lectura que se mueven hacia la derecha

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

METRO=⟨Q,Γ,b,Σ,δ,q0,F⟩,{\displaystyle M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},F\rangle ,}

dónde

Q{\displaystyle Q}es un conjunto finito de estados ;
Γ{\displaystyle \Gamma }es un conjunto finito del alfabeto/símbolos de la cinta ;
b∈Γ{\displaystyle b\in \Gamma }es el símbolo en blanco (el único símbolo que puede aparecer en la cinta infinitamente a menudo en cualquier paso durante el cálculo);
Σ{\displaystyle \Sigma }, un subconjunto deΓ{\displaystyle \Gamma }sin incluir b , es el conjunto de símbolos de entrada ;
δ:Q×Γ→Q×Γ×{R}{\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);
q0∈Q{\displaystyle q_{0}\in Q}es el estado inicial ;
F⊆Q{\displaystyle F\subseteq Q}es el conjunto de estados finales o de aceptación .

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

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

Q={A,B,do,DETENER};{\displaystyle Q=\{A,B,C,{\text{HALT}}\};}
Γ={0,1};{\displaystyle \Gamma =\{0,1\};}
b=0{\displaystyle b=0}, "blanco";
Σ=∅{\displaystyle \Sigma =\varnothing }, conjunto vacío;
δ={\displaystyle \delta =}ver tabla de estados arriba;
q0=A{\displaystyle q_{0}=A}, estado inicial;
F={\displaystyle F=}el conjunto de un solo elemento de estados finales:{DETENER}{\displaystyle \{{\text{HALT}}\}}.

Véase también

Notas

  1. ^ Hopcroft , Motwani y Ullman 2006 .
  2. ↑ McCulloch y Pitts 1943 .
  3. ↑ Rabin y Scott 1959 .
  4. ↑ Bai, Gina R.; Clee, Brian; Shrestha, Nischal; Chapman, Carl; Wright, Cimone; Stolee, Kathryn T. (2019). "Explorando herramientas y estrategias utilizadas durante tareas de composición de expresiones regulares" . En Guéhéneuc, Yann-Gaël; Khomh, Foutse; Sarro, Federica (eds.). Actas de la 27.ª Conferencia Internacional sobre Comprensión de Programas, ICPC 2019, Montreal, QC, Canadá, 25-31 de mayo de 2019. IEEE/ACM. pp. 197–208 . doi : 10.1109/ICPC.2019.00039 . ISBN  978-1-7281-1519-1.
  5. ↑ Mogensen, Torben Ægidius (2011). «Análisis léxico». Introducción al diseño de compiladores . Temas de pregrado en informática. Londres: Springer. pág. 12. doi : 10.1007/978-0-85729-829-4_1 . ISBN  978-0-85729-828-7.
  6. 1 2 Lawson 2004 , pág. 129.
  7. ↑ Sakarovitch 2009 , pág. 228.
  8. ↑ Lawson 2004 , pág. 128.
  9. 1 2 Grusho, AA (1973). "Distribuciones límite de ciertas características de grafos de autómatas aleatorios". Notas Matemáticas de la Academia de Ciencias de la URSS . 4 : 633–637 . doi : 10.1007/BF01095785 . S2CID 121723743 . 
  10. 1 2 Cai, Xing Shi; Devroye, Luc (octubre de 2017). "La estructura gráfica de un autómata determinista elegido al azar". Random Structures & Algorithms . 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. pp. 194–205 .  
  12. ↑ Hopcroft y Ullman 1979 , págs. 59–60.
  13. 1 2 3 Rose, Gene F. (1968). "Cierres que preservan la finitud en familias de lenguajes". Journal of Computer and System Sciences . 2 (2): 148– 168. doi : 10.1016/S0022-0000(68)80029-7 .
  14. 1 2 Spanier, E. (1969). "Gramáticas y lenguajes". American Mathematical Monthly . 76 (4): 335– 342. doi : 10.1080/00029890.1969.12000214 . JSTOR 2316423 . MR 0241205 .  
  15. ↑ Sakarovitch 2009 , pág. 105.
  16. ↑ Lawson 2004 , pág. 63.
  17. ↑ Esparza Estaun, Francisco Javier; Sickert, Salomon; Blondin, Michael (16 de noviembre de 2016). "Operaciones y pruebas en conjuntos: Implementación en autómatas finitos deterministas" (PDF) . Autómatas y lenguajes formales 2017/18 . Archivado del original (PDF) el 8 de agosto de 2018.
  18. ↑ Lawson 2004 , pág. 46.
  19. 1 2 Gold, EM (1978). "Complejidad de la identificación de autómatas a partir de datos dados". Information and Control . 37 (3): 302– 320. doi : 10.1016/S0019-9958(78)90562-4 .
  20. ↑ De Vries, A. (28 de junio de 2014). Autómatas finitos: comportamiento y síntesis . Elsevier. ISBN 9781483297293.
  21. ↑ Lang, Kevin J. (1992). "Los DFA aleatorios se pueden aprender aproximadamente a partir de ejemplos uniformes dispersos". 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 . 
  22. ↑ Oncina, J.; García, P. (1992). "Inferencia de lenguajes regulares en tiempo de actualización polinomial". Reconocimiento de patrones y análisis de imágenes . Serie en percepción automática e inteligencia artificial. Vol. 1. pp. 49–61 . doi : 10.1142/9789812797902_0004 . ISBN   978-981-02-0881-3.
  23. ↑ Lang, Kevin J.; Pearlmutter, Barak A.; Price, Rodney A. (1998). "Resultados de la competición de aprendizaje de DFA Abbadingo one y un nuevo algoritmo de fusión de estados basado en evidencia". Inferencia gramatical (PDF) . Notas de clase en informática. Vol. 1433. págs. 1–12 . doi : 10.1007/BFb0054059 . ISBN   978-3-540-64776-8.
  24. ↑ Adriaans, Pieter; Fernau, Henning; Zaanen, Menno van (23 de septiembre de 2002). Más allá de EDSM | Actas del 6.º Coloquio Internacional sobre Inferencia Gramatical: Algoritmos y Aplicaciones . Springer. págs. 37–48 . ISBN  9783540442394.
  25. ↑ Lucas, SM; Reynolds, TJ (2005). "Aprendizaje de autómatas finitos deterministas con un algoritmo evolutivo de etiquetado de estados inteligente". IEEE Transactions on Pattern Analysis and Machine Intelligence . 27 (7): 1063– 1074. doi : 10.1109/TPAMI.2005.143 . PMID 16013754 . S2CID 14062047 .  
  26. ↑ 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. Lecture Notes in Computer Science. Lecture Notes in Computer Science. Vol. 6339. pp. 66–79 . doi : 10.1007/978-3-642-15488-1_7 . ISBN   978-3-642-15487-4.
  27. ↑ 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 . 
  28. ↑ 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 . Notas de clase en ciencias de la computación. Vol. 8977. págs. 611–622 . doi : 10.1007/978-3-319-15579-1_48 . ISBN   978-3-319-15578-4.
  29. ↑ Davis, Martin; 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: Academic Press, Harcourt, Brace & Company. ISBN  0-12-206382-1.

Referencias

  • Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introducción a la teoría de autómatas, lenguajes y computación (1.ª  ed.). Addison-Wesley. ISBN 0-201-02988-X.( Accesible para usuarios con discapacidades visuales )
  • 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.
  • Lawson, Mark V. (2004). Autómatas finitos . Chapman and Hall/CRC. ISBN 1-58488-255-7. Zbl 1086.68074 . 
  • McCulloch, WS; Pitts, W. (1943). "Un cálculo lógico de las ideas inmanentes en 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. Dev . 3 (2): 114– 125. doi : 10.1147/rd.32.0114 .
  • Sakarovitch, Jacques (2009). Elementos de la teoría de autómatas . Traducido del francés por Reuben Thomas. Cambridge: Cambridge University Press . ISBN 978-0-521-84425-3. Zbl 1188.68177 . 

Lecturas adicionales

  • 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 ) — 1.1 : "Autómatas finitos" págs.  31-47 . 4.1 : "Lenguajes decidibles - Problemas decidibles relacionados con lenguajes regulares" págs.  152-155 . 4.4 : El DFA solo puede aceptar lenguajes regulares