Máquina de estado determinista

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 24 de junio de 2022; las comprobaciones requieren 3 ediciones .

Un autómata finito determinista ( DFA , DFA , eng. deterministic finite automaton , DFSA , eng. deterministic finite-state automaton , ing. deterministic finite-state automaton , DFSM eng. deterministic finite-state machine ), también conocido como reconocedor determinista finito , es un autómata finito que acepta o rechaza los caracteres de una cadena determinada al pasar por la secuencia de estados definida por la cadena [1] . Tiene una sola secuencia de estados durante la operación. McCulloch y Walter Pitts estuvieron entre los primeros investigadores en proponer un concepto similar a una máquina de estado en 1943 [2] [3] .

La figura ilustra una máquina de estados finitos deterministas usando un diagrama de estados . En este ejemplo, hay tres estados: S 0 , S 1 y S 2 (reflejados en la figura por círculos). El autómata acepta una secuencia finita de ceros y unos como entrada. Para cada estado, hay una flecha de transición que va de un estado a otro tanto para el 0 como para el 1. Después de leer un símbolo, el DFA cambia de forma determinista de un estado a otro, siguiendo la flecha de transición. Por ejemplo, si el autómata está en el estado S 0 y el símbolo de entrada es 1, entonces el autómata pasa de forma determinista al estado S 1 . Un DFA tiene un estado inicial (representado gráficamente por una flecha que surge de la nada) desde donde comienza el cálculo y un conjunto de estados finales (representados gráficamente como un círculo doble) que determinan si el cálculo tiene éxito.

DFA se define como un concepto matemático abstracto, pero a menudo se implementa en hardware y software para resolver problemas específicos. Por ejemplo, un DFA puede modelar programas que deciden si una dirección de correo electrónico ingresada por el usuario es válida.

DFA reconoce exactamente una variedad de lenguajes regulares [1] que son útiles para el análisis léxico y la coincidencia de patrones , entre otras cosas . Los DFA se pueden construir a partir de autómatas finitos no deterministas ( NFA ) al reducir los DFA a NFA .

Formal definición

Un autómata finito determinista es una tupla de 5 que consta de $METRO$ ${\ estilo de visualización (Q, \ Sigma, \ delta, q_{0}, F)}$

conjunto finito de estados $q$
un conjunto finito de caracteres de entrada, llamado alfabeto $\Sigma$
función de transición $\delta :Q\times \Sigma \rightarrow Q$
estado inicial $q_{0}\en Q$
conjunto de estados finales $F\subconjunto Q$

Sea una cadena sobre el alfabeto . El autómata acepta una cadena si la secuencia de estado existe con las siguientes condiciones ${\displaystyle w=a_{1}a_{2}...a_{n))$ $\Sigma$ $METRO$ $w$ ${\displaystyle r_{0},r_{1},...,r_{n))$ $q$

$r_{0}=q_{0}$
$r_{i+1}=\delta (r_{i},a_{i+1})$ , por ${\ estilo de visualización i = 0,..., n-1}$
${\ Displaystyle r_ {n} \ en F}$ .

En otras palabras, la primera condición dice que la máquina parte del estado . La segunda condición dice que para un carácter de cadena dado, la máquina pasa de un estado a otro de acuerdo con la función de transición . La última condición dice que la máquina acepta si el último carácter de entrada de la cadena hace que la máquina vaya a uno de los estados finales. De lo contrario, se dice que el autómata rechaza la cadena. El conjunto de cadenas que acepta es un idioma reconocido por el autómata , y este idioma se denota por . $q_{0}$ $w$ $\delta$ $w$ $w$ $METRO$ $METRO$ ${\ estilo de visualización L (M)}$

Una máquina determinista de estados finitos sin estados finales ni estados iniciales se conoce como sistema de transición o semiautómata .

Para una definición formal más completa, ver el artículo " Teoría de Autómatas ".

Autómatas completos e incompletos

De acuerdo con la definición anterior, los autómatas finitos deterministas siempre están completos : definen una transición para cada estado y para cada símbolo de entrada.

Si bien la definición utilizada es la más generalmente aceptada, algunos autores utilizan el término autómata finito determinista para un concepto ligeramente diferente: un autómata que define como máximo una transición (en lugar de exactamente una como en la definición anterior) para cada estado y cada símbolo de entrada. . La función de transición puede definirse parcialmente . Si la transición no está definida, la máquina se detiene.

Ejemplo

El siguiente ejemplo es un DFA binario que requiere que la entrada contenga un número par de ceros. $METRO$

${\ estilo de visualización M = (Q, \ Sigma, \ delta, q_{0}, F)}$ dónde

$Q=\{S_{1},S_{2}\}$
${\ estilo de visualización \ Sigma = \ {0,1 \}}$
${\ estilo de visualización q_ {0} = S_ {1}}$
$F=\{S_{1}\}$ y
$\delta$ definido por la siguiente tabla de saltos :

	0	una
S1 _	S2 _	S1 _
S2 _	S1 _	S2 _

El estado final corresponde a un número par de ceros en la cadena de entrada, mientras que habla de un número impar. 1 en el flujo de entrada no cambia el estado del autómata. Cuando finaliza la cadena de entrada, el estado final indicará si la cadena de entrada contenía un número par de ceros o no. Si la cadena de entrada contiene un número par de ceros, terminará en el estado final , por lo que se aceptará la cadena de entrada. $S_{1}$ $S_{2}$ $METRO$ $S_{1}$

El idioma que se reconoce es un idioma regular definido por una expresión regular , donde es una estrella Kleene , por ejemplo, que significa cualquier número (posiblemente cero) de 1 consecutivos. $METRO$ ((1*) 0 (1*) 0 (1*))**1*

Propiedades de cierre

Si la DFA reconoce los idiomas que se obtienen al aplicar una operación a los idiomas reconocidos por la DFA, se dice que la DFA está cerrada bajo la operación. Los DFA se cierran en las siguientes operaciones.

Una asociación
Intersección [4] (ver figura)
Concatenación
Suma
Cierre Kleene
Apelación
Iteración
Diferencia
Sustitución
homomorfismo

Para cada operación, la construcción óptima, teniendo en cuenta el número de estados, se determina en el estudio de la complejidad posicional .

Debido a que los DFA son equivalentes a autómatas finitos no deterministas (NFA ) , estos cierres se pueden probar utilizando las propiedades de cierre de NFA.

Como un monoide de transiciones

La operación de un DFA dado puede verse como una secuencia de superposiciones de una formulación muy general de funciones de transición sobre sí mismo. Construiremos tal función aquí.

Para un símbolo de entrada dado , puede construir una función de transición definiendo para todos . (Esta técnica se llama curry ). En esta perspectiva , "actúa" sobre el estado Q para producir otro estado. Se puede considerar el resultado de una superposición de funciones , aplicadas sucesivamente a diferentes funciones , etc. Dado un par de letras , se puede definir una nueva función , donde denota una superposición de funciones. ${\ estilo de visualización \ en \ Sigma}$ ${\ estilo de visualización \ delta _ {a}: Q \ flecha derecha Q}$ ${\ estilo de visualización \ delta _ {a} (q) = \ delta (q, a)}$ ${\ estilo de visualización q \ en Q}$ ${\ estilo de visualización \ delta _ {a}}$ ${\ estilo de visualización \ delta _ {a}}$ ${\ estilo de visualización \ delta _ {b))$ ${\ estilo de visualización a, b \ en \ Sigma}$ ${\widehat {\delta }}_{ab}=\delta _{a}\circ \delta _{b}$ $\circ$

Está claro que este proceso puede continuarse recursivamente, dando la siguiente definición recursiva : ${\widehat {\delta }}:Q\times \Sigma ^{\star }\rightarrow Q$

{\widehat {\delta }}(q,\epsilon)=q

, donde está la cadena vacía, y

\epsilon

{\sombrero ancho {\delta }}(q,wa)=\delta ({\sombrero ancho {\delta }}(q,w),a)

, donde y .

w\en \Sigma ^{*},a\en \Sigma

{\ estilo de visualización q \ en Q}

La función está definida para todas las palabras . El trabajo del DFA es una secuencia de superposiciones sobre sí mismo. ${\sombrero ancho {\delta ))$ $w\en \Sigma ^{*}$ ${\sombrero ancho {\delta ))$

La repetición de superposiciones de funciones forma un monoide . Para las funciones de transición, este monoide se conoce como monoide de transición o, a veces, como semigrupo de transformación . La construcción se puede invertir: si se da , se puede reconstruir , por lo que las dos descripciones son equivalentes. ${\sombrero ancho {\delta ))$ $\delta$

Autómatas locales

Un autómata local es un DFA en el que todos los arcos con la misma etiqueta conducen al mismo vértice. Los autómatas locales aceptan la clase de lenguajes formales , para los cuales la pertenencia de una palabra a un lenguaje está determinada por una "ventana deslizante" de longitud dos sobre la palabra [5] [6]

El gráfico de Myhill sobre el alfabeto A es un gráfico dirigido con el conjunto de vértices A y un subconjunto de vértices etiquetados como "inicial" y "terminal". El lenguaje aceptado por el gráfico de Myhill es el conjunto de caminos dirigidos desde el vértice inicial hasta el vértice final; el gráfico funciona entonces como un autómata [5] . La clase de idiomas que perciben los gráficos de Myhill es la clase de idiomas locales [7] .

Estocástico en DFA

Cuando se ignoran el estado inicial y los estados finales, un DFA con estados y un alfabeto de tamaño se puede considerar como un dígrafo de vértice en el que todos los vértices tienen arcos salientes etiquetados (dígrafo de resultado ). Se sabe que cuando es un número entero fijo, con alta probabilidad el mayor componente fuertemente conexo ( SCC), en el que el dígrafo con resultados se elige uniformemente al azar, tiene un tamaño lineal y se puede alcanzar desde cualquier vértice [8] . También se demostró que a medida que , aumenta a medida que , todo el dígrafo tiene una transición de fase a una conexión fuerte, similar al modelo Erdős-Rényi para conectividad [9] . $norte$ $k$ $norte$ $k$ ${\ estilo de visualización 1, \ puntos, k}$ $k$ $k\geqslant 2$ $k$ $k$ $norte$

En un DFA aleatorio, el número máximo de vértices alcanzables desde un vértice con alta probabilidad es muy cercano al número de vértices en el componente fuertemente conectado más grande [8] [10] . Esto también es cierto para el subgrafo generado más grande con un mínimo de grado uno, que se puede considerar como una versión dirigida del -kernel [9] . $una$

Ventajas y desventajas

DFA es uno de los modelos computacionales más prácticos, ya que existe un algoritmo en línea trivial tiempo lineal y memoria constante para simular DFA en el flujo de entrada. También hay algoritmos de búsqueda de reconocimiento de DFA eficientes:

finalización del idioma reconocido por el DFA dado.
unión/intersección de lenguas reconocidas por dos DFA dados.

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

si el DFA acepta cualquier cadena (tarea de prueba vacía)
si el DFA acepta todas las filas (problema de prueba de universalidad)
si dos DFA aceptan el mismo idioma (problema de prueba de equivalencia)
si un idioma reconocido por un DFA está contenido en un idioma reconocido por otro DFA (tarea de prueba de inclusión)
DFA con un número mínimo de estados para un idioma regular particular (problema de minimización)

Los DFA son computacionalmente equivalentes a los autómatas finitos no deterministas (NFA, nondeterministic finite automata , NFA). Esto se debe a que, en primer lugar, cualquier DFA es también un NFA, por lo que un NFA puede hacer cualquier cosa que pueda hacer un DFA. Además, dada una NFA, al reducir una DFA a una NFA se puede construir una DFA que reconozca el mismo lenguaje que la NFA, aunque una DFA puede tener exponencialmente más estados que una NFA [11] [12] . Sin embargo, incluso si los NFA son computacionalmente equivalentes a los DFA, los problemas anteriores no se resuelven necesariamente de manera eficiente para los NFA. El problema de no universalidad para un NFA tiene una complejidad PSPACE , ya que hay pequeños NFA con las palabras de menor tamaño exponencial para rechazar. Un DFA es universal si y solo si todos los estados son finitos, pero esto no es cierto para un NFA. Los problemas de equivalencia, inclusión y minimización también tienen complejidad PSPACE , ya que requieren la formación del complemento de la NFA, lo que conduce a una explosión de tamaño exponencial [13] .

Por otro lado, las máquinas de estado están severamente limitadas en los lenguajes que reconocen. DFA no puede reconocer muchos lenguajes simples, incluido cualquier problema que requiera más que memoria constante para resolverse. Un ejemplo clásico de un lenguaje simple que ningún DFA puede reconocer son los corchetes o el lenguaje Dyck , es decir, un lenguaje que consta de corchetes debidamente espaciados, como en la palabra "(()())". Es intuitivamente claro que ningún DFA puede reconocer el lenguaje de Dyck, ya que los DFA no pueden hacer cálculos: los autómatas como los DFA necesitan un estado que represente cualquier número posible de paréntesis "abiertos", lo que significa que deben tener un número ilimitado de estados. Otro ejemplo simple es un lenguaje que consta de cadenas de la forma de un número finito pero arbitrariamente grande de letras a seguidas por un número igual de letras b [14] . ${\ estilo de visualización a^{n}b^{n))$

Véase también

Autómata finito acíclico determinista
minimización de DFA
Lógica monádica de segundo orden
Reducción de NFA a DFA
Máquina de estado cuántica
Máquinas de Turing con cabezal de lectura moviéndose hacia la derecha
Problema de separación de palabras
máquina de Turing
Máquina finita determinista bidireccional

Notas

↑ 1 2 Hopcroft, Motwani, Ullman, 2001 .
↑ McCulloch, Pitts, 1943 .
↑ Rabin, Scott, 1959 .
↑ Hopcroft, Ullman, 1979 , pág. 59-60.
↑ 12 Lawson , 2004 , pág. 129.
↑ Sakarovitch, 2009 , pág. 228.
↑ Lawson, 2004 , pág. 128.
↑ 1 2 Grusho, 1973 , pág. 633–637.
↑ 1 2 Cai, Devroye, 2017 , pág. 428–458.
↑ Carayol, Nicaud, 2012 , p. 194–205.
↑ Sakarovitch, 2009 , pág. 105.
↑ Lawson, 2004 , pág. 63.
↑ Startseite-Lehrstuhl für Theoretische Informatik . Consultado el 6 de febrero de 2020. Archivado desde el original el 8 de agosto de 2018. (indefinido)
↑ Lawson, 2004 , pág. 46.

Literatura

John Hopcroft , Rajeev Motwani , Jeffrey Ullman . Introducción a la teoría de autómatas, lenguajes y computación . - 2. - Addison Wesley , 2001. - ISBN 0-201-44124-1 .
Marcos V. Lawson. Automático finito. - Chapman and Hall/CRC, 2004. - ISBN 1-58488-255-7 .
McCulloch W.S., Pitts W. Un cálculo lógico de las ideas inmanentes en la actividad nerviosa // Boletín de biofísica matemática. - 1943. - V. 5 , núm. 4 . — S. 115–133 . -doi : 10.1007/ BF02478259 . Archivado desde el original el 12 de abril de 2019.
Rabin MO, Scott D. Autómatas finitos y sus problemas de decisión. // IBM J.Res. desarrollador - 1959. - T. 3 , nº. 2 . — S. 114–125 . -doi : 10.1147/ rd.32.0114 .
Jacques Sakarovitch. Elementos de la teoría de los autómatas / Traducido del francés por Reuben Thomas. - Cambridge: Cambridge University Press , 2009. - ISBN 978-0-521-84425-3 .
Michael Sipser. Introducción a la Teoría de la Computación . - Boston: PWS, 1997. - ISBN 0-534-94728-X . Sección 1.1: Autómatas finitos, págs. 31-47. Subsección "Problemas decidibles relacionados con lenguajes regulares" de la sección 4.1: Lenguajes decidibles, pp. 152-155.4.4 DFA solo puede aceptar lenguaje normal
John E. Hopcroft, Jeffrey D. Ullman. Introducción a la teoría de autómatas, lenguajes y computación . - Lectura/MA: Addison-Wesley, 1979. - ISBN 0-201-02988-X .
- Traducido por John Hopcroft, Rajiv Motwani, Geoffrey Ullman. Introducción a la teoría de autómatas, lenguajes y computaciones. - Moscú, San Petersburgo, Kiev: Williams, 2002. - ISBN 5-8459-0261-4 .
Grusho A. A. Sobre las distribuciones límite de algunas características de grafos de autómatas aleatorios // Matem. notas - 1973. - T. 4 . - P. 133-141, 633-637. -doi : 10.1007/ BF01095785 .
Xing Shi Cai, Luc Devroye. La estructura gráfica de un autómata determinista elegido al azar // Estructuras aleatorias y algoritmos. - 2017. - Octubre ( vol. 51 , número 3 ). -doi : 10.1002/ rsa.20707 .
Arnaud Carayol, Cyril Nicaud. Distribución del número de estados accesibles en un autómata determinista aleatorio // STACS'12 (29th Symposium on Theoretical Aspects of Computer Science) . - París, Francia, 2012. - T. 14.

Lenguajes formales y gramáticas formales
Conceptos generales	Jerarquía de Chomsky Alfabeto Palabra
tipo 0	Gramática ilimitada máquina de Turing lenguaje enumerado Lenguaje resoluble
Tipo 1	Gramática sensible al contexto Lenguaje sensible al contexto Autómata linealmente acotado
Tipo 2	gramática libre de contexto gramática ambigua lenguaje libre de contexto Autómata pushdown ( determinista ) Lema de crecimiento Lema de Ogden teorema de Cook
tipo 3	gramática regular lenguaje normal Expresión regular Máquina de estados ( determinista , no determinista ) minimización de DFA Determinación de NFA Teorema de Myhill-Nerode
analizando	analizador LL analizador LR Método de descenso recursivo Algoritmo Kok-Younger-Kasami