En términos muy sencillos por favor, todos los recursos que estoy encontrando hablan de tuplas y demás y sólo necesito una explicación sencilla que pueda recordar fácilmente porque sigo confundiéndolos.
Cada entrada a un DFA o NFA afecta al estado del autómata: si estaba en el estado $q$ inmediatamente antes de la entrada, o bien estará en algún estado $q'$ después de la entrada, o la entrada hará que se ahogue. (Tenga en cuenta que $q'$ puede ser el mismo que $q$ .) Supongamos que tenemos un autómata en un estado $q$ . La diferencia de comportamiento entre un DFA y un NFA es esta:
Si es un DFA, cada posible entrada determina el estado resultante $q'$ de forma única. Cada entrada provoca un cambio de estado, y el nuevo estado está completamente determinado por la entrada. Además, el autómata puede cambiar de estado sólo después de leer una entrada.
Si se trata de un NFA, algunas entradas pueden permitir una elección de estados resultantes, y otras pueden hacer que el autómata se ahogue, porque hay no nuevo estado correspondiente a esa entrada. Además, el autómata puede construirse de forma que pueda cambiar de estado a algún nuevo estado $q'$ sin leer ninguna entrada.
Como consecuencia de esta diferencia de comportamiento, las AFD y las AFN difieren en otro aspecto muy importante.
Si se inicia un DFA en su estado inicial y se introduce alguna palabra $w$ el estado $q$ en el que termina el DFA está completamente determinado por $w$ : introducción de $w$ al DFA siempre hará que acabe en el estado $q$ . Esto es lo que significa llamarlo determinista .
Si se inicia un NFA en su estado inicial y se introduce alguna palabra $w$ , puede haber varios estados posibles en los que puede terminar, ya que algunas de las entradas a lo largo del camino pueden haber permitido una elección de cambios de estado. En consecuencia, no se puede predecir de $w$ sólo en qué estado terminará el autómata; esto es lo que significa llamarlo no determinista . (Y en realidad es un poco peor de lo que he indicado, ya que también se permite que un NFA tenga más de un estado inicial).
Por último, estas diferencias afectan a la forma de determinar qué palabras son aceptadas (o reconocidas) por un autómata.
Si es un DFA, sabemos que cada palabra determina completamente el estado final del autómata, y decimos que la palabra es aceptada si ese estado es un estado aceptor.
Si es un NFA, puede haber varios estados finales posibles que podrían resultar de la lectura de una palabra dada; mientras al menos uno de ellos sea un estado aceptor, decimos que el autómata acepta la palabra.
Lo que he descrito de manera informal es la visión de un AFN que más se parece a un AFD y que creo que explica mejor por qué se llama no determinista . Sin embargo, hay otra forma de ver las NFAs: también es posible pensar en una NFA como si estuviera en múltiples estados a la vez, como si estuviera haciendo todas las elecciones posibles en cada entrada. Si se piensa en ello en estos términos, se puede decir que acepta una palabra siempre que al menos uno de los estados en los que termina después de leer esa palabra sea un estado aceptor. Este punto de vista es quizás más útil para entender el algoritmo usado para convertir un NFA en un DFA equivalente.
Gracias por la respuesta detallada. Dices que un automatismo finito no determinista puede cambiar de estado sin leer ninguna entrada, ¿significa eso que un automatismo finito determinista TIENE que tener todas las transiciones posibles en cada estado? (Porque estoy asumiendo que son opuestos).
@Clay: Sí, en cada estado un AFD debe tener una transición para cada símbolo del alfabeto de entrada. No puede tener ninguna $\epsilon$ Sin embargo, las transiciones sin entrada son las más importantes.
¿Puedes aclarar lo que quieres decir con ahogar la NFA? ¿Se refiere a la vinculación con el mismo estado, o a la finalización sin éxito del NFA?
Los autómatas son máquinas abstractas que tienen un conjunto finito de estados. Dada una entrada, pasan de un estado a otro. Se puede pensar en ellos como si fueran diagramas de flujo.
Un AFN es un autómata finito no determinista. No determinista significa que puede transitar y estar en varios estados a la vez (es decir, para una entrada determinada).
Un DFA es un autómata finito determinista. Determinista significa que sólo puede estar en, y la transición a, un estado a la vez (es decir, para alguna entrada dada).
La principal diferencia es que una NFA suele ser mucho más eficiente.
Para cada símbolo del alfabeto, sólo hay una transición de estado en DFA .
No es necesario especificar cómo el NFA reaccionar según algún símbolo.
DFA no puede utilizar la transición a cadena vacía.
NFA puede utilizar la transición a cadena vacía.
DFA puede entenderse como una sola máquina.
NFA puede entenderse como múltiples maquinitas que computan al mismo tiempo.
DFA rechazará la cadena si termina en un estado distinto al de aceptación.
Si todas las ramas de NFA muere o rechaza la cadena, podemos decir que NFA rechazar la cadena.
1. "DFA" significa "Autómata Finito Determinista", mientras que "NFA" significa "Autómata Finito No Determinista".
2.Ambos son funciones de transición de autómatas. En el DFA el siguiente estado posible es un conjunto distinto, mientras que en el NFA cada par de estado y símbolo de entrada puede tener muchos estados siguientes posibles.
3.NFA puede usar una transición de cadena vacía, mientras que DFA no puede usar una transición de cadena vacía.
4.NFA es más fácil de construir, mientras que es más difícil construir DFA.
5.El backtracking está permitido en DFA, mientras que en NFA puede o no estar permitido.
6.DFA requiere más espacio, mientras que NFA requiere menos espacio.
7.Mientras que 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.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
6 votos
N = no determinista, D = determinista. ¿Qué aspectos confundes de los autómatas? Ignora las tuplas: son una representación de bajo nivel pensada para demostrar cosas y hacer afirmaciones precisas, no para la intuición humana.