¿Cuál es la diferencia entre autómatas deterministas y no deterministas de estado finito?

Ambas son funciones de transición de autómatas. En DFA, el siguiente estado posible se establece claramente, mientras que en NFA cada par de estado y símbolo de entrada puede tener muchos estados siguientes posibles.

NFA puede usar la transición de cadena vacía, mientras que DFA no puede usar la transición de cadena vacía.

NFA es más fácil de construir, mientras que es más difícil construir DFA.

El retroceso está permitido en DFA mientras que en NFA puede o no estar permitido.

DFA requiere más espacio, mientras que NFA requiere menos espacio.

Si bien DFA se puede entender como una máquina y se puede construir una máquina DFA para cada entrada y salida, NFA se puede entender como varias máquinas pequeñas que computan juntas, y no hay posibilidad de construir una máquina NFA para cada entrada y salida.

Un autómata pushdown (PDA) es básicamente un autómata de estado finito con el elemento de memoria agregado, que es una pila.

Con esa definición fuera del camino, veamos lo que realmente significa no determinismo.

Cuando se dice que una máquina no es determinista, tiene el poder del paralelismo infinito. Significa que cuando se le da una opción, la máquina se clonará mágicamente y cada copia tomará un camino diferente. Un autómata finito no determinista (NFA), por ejemplo, puede verse en múltiples estados a la vez debido a sus poderes no deterministas. ¡Un NFA puede comer su pastel y tenerlo también! (Así puede cualquier máquina no determinista).

En el caso de sus Autómatas finitos deterministas (DFA) regulares, agregar no determinismo no agrega ningún poder computacional en absoluto.
¿Por qué?
¡Debido a que puede ver el conjunto de todos los estados, el NFA está simultáneamente en conjunto, como un solo estado de un DFA equivalente! Algo así como ver a VEINTE leones como UN orgullo de leones.
En general, cualquier NFA se puede convertir en un DFA equivalente.

Ah, pero las aguas no son tan claras cuando se trata de PDA.

Como cada PDA tiene una pila asociada, no puede asumir que es posible imitar un NPDA usando un DPDA.
Incluso si vio todos los estados en los que se encuentra el NPDA simultáneamente, como un solo estado de un DPDA correspondiente, no hay forma de que pueda combinar todas las diferentes pilas (de cada clon) en una sola pila que pertenece al DPDA correspondiente.

Es por eso que el no determinismo agrega potencia computacional adicional a las PDA.

Aunque no respondí la pregunta explícitamente, deberías haber podido inferir las implicaciones tú mismo. En caso de que no lo hayas hecho:

Un autómata pushdown no determinista es mejor en cuanto a computabilidad que uno determinista. Puede aceptar un conjunto de idiomas más grande que un autómata determinista pushdown.

PS El no determinismo no tiene un efecto similar para las máquinas de Turing, pero esa es una historia para otro día.

En un autómata determinista de estado finito (DFA), cada movimiento solo tiene una opción para el siguiente estado del dispositivo, dado el estado actual y la siguiente entrada. Después de procesar toda la cadena de entrada, si termina en un estado final (a veces llamado estado de aceptación), entonces la cadena de entrada está en el idioma aceptado por el autómata de estado finito.

En un autómata de estado finito no determinista (NDFA), cada movimiento puede tener más de una opción para el siguiente estado del dispositivo. Entonces, ¿cómo podemos determinar si la cadena de entrada está en el lenguaje aceptado por el autómata de estado finito no determinista? Mientras algún conjunto de opciones conduzca a un estado de aceptación, se considera que la cadena de entrada está en el idioma. Por lo tanto, puede probar todos los movimientos posibles (que son finitos en número), y siempre que al menos un conjunto de opciones conduzca a un estado de aceptación, la cadena de entrada se considera que está en el idioma.

La buena noticia es que los idiomas reconocidos por NDFA son los mismos que los reconocidos por un DFA.

Y hay algoritmos que convertirán un NDFA en un DFA equivalente. Y eso es lo que quieres hacer.

Si los NDFA son equivalentes a los DFA, ¿por qué usaríamos los NDFA?

Dado un lenguaje que deseamos construir un DFA para reconocer cadenas en el idioma, a menudo es más fácil crear un NDFA que un DFA.

Luego puede usar el algoritmo para convertir el NDFA a un DFA equivalente.

En general, lo que probablemente sepa, un autómata finito tiene un conjunto de estados, comienza en un estado de inicio y lee una cadena de entrada carácter por carácter, cada carácter hace que cambie de estado según el carácter que lea y el estado en que se encuentre. estaba anteriormente en (par de caracteres de estado); Esto se llama función de transición o relación de transición. Algunos estados también pueden tener transiciones ε, que son estados a los que puede ir la máquina sin leer ningún carácter. Un cierto conjunto de estados se designan como estados de aceptación; si el autómata finito acepta o rechaza depende de si está en un estado de aceptación o de rechazo después de leer la cadena completa. La descripción que acabo de dar fue, intencionalmente, lo suficientemente vaga como para aplicarla tanto a autómatas finitos deterministas como no deterministas, a los que me referiré como DFA y NFA, respectivamente, de aquí en adelante.

En un autómata finito no determinista, la relación de transición especifica cualquier número, incluidos 0, 1, 2 o más, posibles estados a los que el NFA puede hacer la transición para cada par de caracteres de estado. La forma en que decide cuál tomar no está definida ni es relevante para el concepto abstracto, pero puede pretender que elige al azar de manera uniforme. Esto puede producir muchas rutas de cálculo diferentes para la misma cadena de entrada; y decimos que un NFA acepta una cadena si al menos una de esas rutas termina en un estado de aceptación.

En cierto sentido, solo podemos decir que un autómata finito determinista es uno que no es determinista, donde la función de transición especifica solo un estado futuro para cada par de caracteres de estado, y por lo tanto solo hay una ruta de cálculo en cualquier cadena de entrada dada. Si termina en un estado de aceptación designado, la máquina acepta. Entonces, la diferencia clave es si la ruta de cálculo está determinada por la cadena de entrada, o si hay algún no determinismo adicional involucrado. Pero hay otra diferencia, y tiene que ver con el tamaño.

Obviamente, cualquier DFA puede convertirse en un “NFA sin no determinismo”, por lo que cualquier lenguaje aceptado por un DFA puede ser aceptado por un NFA. Dado un NFA, en cualquier punto de la cadena podemos ver todas las rutas de cálculo hasta este punto, y el conjunto de estados en los que se encuentra al menos una ruta de cálculo; y estos conjuntos de estados pueden considerarse los estados de un DFA, ya que esta transición es determinista. (Si no es obvio a partir de esta explicación, piénselo un poco.) Por lo tanto, los idiomas reconocidos por los DFA y los reconocidos por los NFA son idénticos. Sin embargo, si toma un NFA con n estados y lo convierte en un DFA usando este método, ese DFA tendrá 2 ^ n estados, y hay algunos idiomas en los que no puede ser más eficiente que eso. También está comprobado que los lenguajes que pueden describirse mediante expresiones regulares tienen el mismo conjunto que los que pueden ser reconocidos por DFA o NFA, pero dada una expresión regular de longitud n, el NFA más pequeño tiene estados O (n), mientras que el más pequeño DFA en general tiene estados O (2 ^ n).

No profundiza solo una explicación intuitiva básica

Cada elemento de LHS se asigna solo una vez a un elemento a la derecha, es decir, al recibir una entrada particular, realiza una sola transición. Al dar la entrada a al estado A, irá al estado B

Al menos 1 elemento en LHS se puede asignar a más de 1 elemento en RHS, como aquí, al dar la entrada a al estado A, irá al estado B y C. El cambio de estado de A no se puede predecir.

Ambos tipos de autómatas se definen como 5-tuplas de la forma

[matemáticas] (Q, \ Sigma, \ delta, q_0, F) [/ matemáticas]

donde [math] Q [/ math] es un conjunto finito de estados, [math] \ Sigma [/ math] es el alfabeto de entrada, [math] \ delta [/ math] es una función de transición, [math] q_0 \ in Q [/ math] es un estado de inicio designado y [math] F \ subseteq Q [/ math] es un conjunto de estados finales.

La diferencia radica en la definición de la función de transición y, debido a esta diferencia, también en la forma en que se define la aceptación.

La función de transición nos dice qué estados del autómata son los estados sucesores, dado un símbolo de entrada [math] a [/ math] y un estado actual [math] q [/ math].

Un autómata determinista de estado finito (DFA) es, como su nombre lo indica, determinista. Aquí, [math] \ delta (q, a) [/ math] es un estado único. Entonces, el tipo de [math] \ delta [/ math] es

[matemáticas] \ delta: Q \ veces \ Sigma \ rightarrow Q [/ matemáticas]

Podemos definir la función de transición extendida para cadenas como

[matemáticas] \ delta ^ * (q, x) = \ begin {cases} q & \ mbox {if} x = \ varepsilon \\ \ delta (\ delta ^ * (q, y), a) & \ mbox { if} x = ya \ mbox {para alguna cadena} y \ end {cases} [/ math]

[math] \ delta ^ * (q, x) [/ math] es el estado único en el que terminará el autómata, si comenzamos en el estado [math] q [/ math] y leemos la cadena [math] x [ /mates].

Una cadena [math] x [/ math] es aceptada por un DFA si [math] \ delta (q_0, x) \ en F [/ math], es decir, si el DFA al comenzar en el estado inicial terminará en un estado final si dejamos que el DFA lea [math] x [/ math].

Un autómata de estado finito (NFA) no determinista no tiene este requisito . Aquí, [math] \ delta (q, a) [/ math] es un conjunto de estados sucesores , y este conjunto de estados sucesores puede estar vacío . Además, la función de transición también es no determinista en otro sentido: permitimos transiciones si no se lee ningún símbolo de entrada; pensamos en esto como leer la cadena vacía [math] \ varepsilon [/ math].

Entonces el tipo de [math] \ delta [/ math] es ahora

[matemáticas] \ delta: Q \ times \ Sigma \ cup \ {\ varepsilon \} \ rightarrow \ mathcal {P} (Q) [/ math]

donde [matemáticas] \ matemáticas {P} (Q) [/ matemáticas]

es el conjunto de potencia de [math] Q [/ math].

En otras palabras, deberíamos pensar en un DFA como un tipo de NFA muy aburrido.

El autómata simple a continuación no es un DFA a pesar de que parece que el estado sucesor es único para cada símbolo, ya que para algunos estados, hay símbolos para los que no se define ningún estado sucesor. Entre otras cosas, tenemos que [math] \ delta (q_0, b) = \ emptyset [/ math].

La definición de la función de transición extendida para cadenas es un poco más complicada para un NFA.

[matemáticas] \ delta ^ * (q, x) = \ begin {cases} \ {q \} & \ mbox {if} x = \ varepsilon \\ \ bigcup_ {q ‘\ in \ delta ^ * (q, y )} \ delta (q ‘, a) & \ mbox {if} x = ya \ mbox {para alguna cadena} y \ end {cases} [/ math]

[math] \ delta ^ * (q, x) [/ math] ahora es el conjunto de estados en los que terminará el autómata, si comenzamos en el estado [math] q [/ math] y leemos la cadena [math] x [/ matemáticas]. (Tenga en cuenta que, debido a la forma en que hemos definido [math] \ delta ^ * [/ math], este conjunto de estados puede estar vacío).

Una cadena [math] x [/ math] es aceptada por un NFA si [math] \ delta (q_0, x) \ cap F \ neq \ emptyset [/ math], es decir, si al menos uno de los estados que NFA puede terminar comenzando en el estado inicial, será un estado final si dejamos que NFA lea [math] x [/ math].

Cada entrada a un DFA o un NFA afecta el estado del autómata. Si obtiene una entrada y el utomaton está en un estado x, puede ir a x ‘o no puede encontrar ningún otro estado para ir.

En un sistema determinista, para cada entrada hay un estado o / p determinado de forma única. el autómata leerá la entrada y pasará a un nuevo estado.

Entonces, si tiene una palabra, cada vez que el autómata termine en el mismo estado.

DFA acepta la palabra si termina en estado aceptado.

En un sistema no determinista, para una entrada puede haber una elección de estados y se puede configurar un salto a x ‘incluso sin aceptar ninguna entrada.

Entonces, si tiene una palabra, el autómata puede o no terminar en el mismo estado, ya que puede haber una selección de estados disponibles para una entrada específica.

NFA acepta la palabra si alguno de los estados en los que termina es un estado aceptado.

Un autómata de pushdown determinístico al ver un carácter de entrada y la parte superior del símbolo de la pila puede hacer algo definitivo significa que insertará un nuevo símbolo o reemplazará el símbolo superior por el carácter nulo bt en caso de autómatas de pushdown no determinístico, puede hacer más de uno .