Autómata finito determinista

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 aceptador finito determinista (DFA), máquina determinista de estados finitos (DFSM), o autómata determinista de estados finitos (< b>DFSA): es una máquina de estados finitos que acepta o rechaza una cadena determinada de símbolos, ejecutando una secuencia de estados determinada únicamente por la cadena. 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.

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

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.

Definición 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 el alfabeto .
• a) Función de transición δ: Q × Governing → Q
• un estado inicial o inicial ${displaystyle q_{0}in Q}$
• un conjunto de estados de aceptación ${displaystyle Fsubseteq Q}$

Sea w = a₁a_{2< /sub>…an} sea una cadena sobre el alfabeto Σ. El autómata M acepta la cadena w< /span> si es una secuencia de estados, r₀, r₁, …, r_n, existe 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 de inicio 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 cadena. El conjunto de cadenas que M acepta es el idioma reconocido por M y este idioma se indica con 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 los autómatas.

Ejemplo

El siguiente ejemplo es de un DFA M, con un alfabeto binario, que requiere que la entrada contenga un número par de 0s.

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

• Q =S₁, S₂}
• .
• q₀ = S₁
• F =S₁} y
• δ se define en el siguiente cuadro de transición estatal:

	0	1
S1	S2	S1
S2	S1	S2

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 finalizará en el estado S₁, un estado de aceptación, por lo que se aceptará la cadena de entrada.

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 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. 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 sobre la palabra.

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&#. 34; y "terminar". 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. La clase de idiomas aceptada por Myhill Graphs es la clase de idiomas locales.

Aleatoriedad

Cuando se ignoran los estados de inicio y aceptación, un DFA de n estados y un alfabeto de tamaño k puede verse como un dígrafo de n vértices en los que todos los vértices tienen k arcos externos etiquetados 1,…, k (un dígrafo de salida k). Se sabe que cuando k ≥ 2 es un entero fijo, con alta probabilidad, el mayor componente fuertemente conectado (SCC) en tal k-digrafo elegido uniformemente al azar es de tamaño lineal y puede ser alcanzado por todos los vértices. También se ha demostrado que si se permite que k aumente como n aumenta, 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.

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. Esto también es válido para el subdígrafo inducido más grande de grado uno mínimo, que puede verse como una versión dirigida de 1 núcleo.

Propiedades de cierre

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.

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 ${displaystyle ain Sigma }$, se puede construir una función de transición ${displaystyle delta ¿Por qué?$ definiendo ${displaystyle delta _{a}(q)=delta (q,a)}$ para todos ${displaystyle qin Q}$. (Este truco se llama currying.) Desde esta perspectiva, ${displaystyle delta _{a}$ "actúa" en un estado en Q para producir otro estado. A continuación, se puede considerar el resultado de la composición de la función aplicada repetidamente a las diversas funciones ${displaystyle delta _{a}$, ${displaystyle delta _{b}$Y así. Dado un par de letras ${displaystyle a,bin Sigma }$, uno puede definir una nueva función ${displaystyle {widehat {delta }_{ab}=delta ################################################################################################################################################################################################################################################################ ¿Qué?$, donde ${displaystyle circ }$ denota composición de la función.

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

${displaystyle {widehat {delta}(q,epsilon)=q}$, donde ${displaystyle epsilon }$ es la cuerda vacía y

${displaystyle {widehat {delta }(q,wa)=delta _{a}({widehat {delta }}(q,w)}}$, donde ${displaystyle win Sigma ^{*},ain Sigma }$ y ${displaystyle qin Q}$.

${displaystyle {widehat {delta }$ se define para todas las palabras ${displaystyle win Sigma ^{*}$. Una carrera del DFA es una secuencia de composiciones de ${displaystyle {widehat {delta }$ con ella misma.

La composición de función repetida forma un monoide. Para las funciones de transición, este monoide es conocido como el monoide de transición, o a veces el transformación semigrupo. La construcción también se puede revertir: dada una ${displaystyle {widehat {delta }$, uno puede reconstruir un ${displaystyle delta }$, y por lo tanto las dos descripciones son equivalentes.

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 dado.
• la unión/intersección de los idiomas reconocidos por dos DFA 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 DFA acepta algún tipo de cadena (Problema del Empleo)
• si un DFA acepta todas las cadenas (Problema de la Universidad)
• si dos DFA reconocen el mismo idioma (Problema de Calidad)
• si el idioma reconocido por un DFA se incluye 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. 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.

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 similar a DFA necesita tener un estado que represente cualquier número posible de códigos "actualmente abiertos" paréntesis, 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, seguidas de un número igual de b's.

Identificación DFA a partir de palabras etiquetadas

Dado un conjunto de positivo palabras ${displaystyle S^{+}subset Sigma ^{*}$ y un conjunto de negativo palabras ${displaystyle S^{-}subset Sigma ^{*}$ uno puede construir un DFA que acepta todas las palabras ${displaystyle S^{+}$ y rechaza todas las palabras de ${displaystyle - Sí.$: este problema se llama DFA identification (síntesis, aprendizaje). Mientras tanto algunos El DFA se puede construir en tiempo lineal, el problema de identificar un DFA con el número mínimo de estados es NP-completo. El primer algoritmo para la identificación mínima DFA ha sido propuesto por Trakhtenbrot y Barzdin y se llama el TB-algorithm. Sin embargo, el TB-algorithm asume que todas las palabras de ${displaystyle Sigma$ hasta una longitud dada están contenidas en ${displaystyle S^{+}cup - Sí.$.

Más tarde, K. Lang propuso una extensión del TB-algorithm que no utiliza ninguna suposición sobre ${displaystyle S^{+}$ y ${displaystyle - Sí.$, el Traxbar algoritmo. Sin embargo, Traxbar no garantiza la mínimaidad del DFA construido. En su trabajo E.M. Gold también propuso un algoritmo heurístico para la identificación mínima de DFA. El algoritmo de oro supone que ${displaystyle S^{+}$ y ${displaystyle - Sí.$ contiene un característico de la lengua regular; de lo contrario, el DFA construido será incompatible con ${displaystyle S^{+}$ o ${displaystyle - Sí.$. Otros algoritmos de identificación notables de DFA incluyen el algoritmo de RPNI, el algoritmo de medición de evidencia de Blue-Fringe, and Windowed-EDSM. Otra dirección de investigación es la aplicación de algoritmos evolutivos: el algoritmo evolutivo de etiquetado de estado inteligente permitió resolver un problema de identificación DFA modificado en el que los datos de entrenamiento (conjuntos) ${displaystyle S^{+}$ y ${displaystyle - Sí.$) es Noisy en el sentido de que algunas palabras se atribuyen a clases erróneas.

Otro paso adelante se debe a la aplicación de los solvers SAT por Marjin J. H. Heule y S. Verwer: el problema mínimo de identificación DFA se reduce a decidir la satisfiabilidad de una fórmula booleana. La idea principal es construir un aceptador de árbol prefijo aumentado (un trío que contenga todas las palabras de entrada con las etiquetas correspondientes) basado en los conjuntos de entrada y reducir el problema de encontrar un DFA con ${displaystyle C}$ estados a para colorear el árbol vértices con ${displaystyle C}$ estados de tal manera que cuando las vértices con un color se fusionan a un estado, el autómata generado es determinista y cumple con ${displaystyle S^{+}$ y ${displaystyle - Sí.$. Aunque este enfoque permite encontrar el mínimo DFA, 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 incrementado con la realización de varios pasos del algoritmo EDSM antes de la ejecución del solucionador SAT: el algoritmo DFASAT. Esto permite reducir el espacio de búsqueda del problema, pero conduce a la pérdida de la garantía mínima. Otra manera de reducir el espacio de búsqueda ha sido propuesta por Ulyantsev et al. por medio de nuevos predicados de ruptura de simetría basados en el algoritmo de búsqueda de la primera: los estados de DFA buscados se limitan a ser numerados según el algoritmo BFS lanzado desde el estado inicial. Este enfoque reduce el espacio de búsqueda por ${displaystyle C!}$ eliminando la automata isomorfa.

Modelos equivalentes

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

máquinas de Turing de solo lectura con movimiento 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. La definición basada en una cinta infinita es una tupla de 7

${displaystyle M=langle Q,Gammab,Sigmadeltaq_{0},Frangle}$

dónde

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

${displaystyle "Gamma"$ es un conjunto finito del alfabeto/símbolos;

${displaystyle bin Gamma }$ es símbolo en blanco (el único símbolo permitido a ocurrir en la cinta infinitamente a menudo en cualquier paso durante la computación);

${displaystyle Sigma$, un subconjunto de ${displaystyle "Gamma"$ no incluido b, es el conjunto de símbolos de entrada;

${displaystyle delta: Qtimes Gamma to Qtimes Gamma times {R}$ es una función llamada función de transición, R es un movimiento correcto (un cambio de derecho);

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

${displaystyle Fsubseteq Q}$ es el conjunto de final o aceptar estados.

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 estar 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}$, "negro";

${displaystyle Sigma = 'varnothing }$, conjunto vacío;

${displaystyle delta =}$ véase la tabla estatal anterior;

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

${displaystyle F=$ el único elemento conjunto de estados finales: ${displaystyle{text {f}}}}$.