¿Cómo diferenciar entre DFA y NDFA

determinista y autómatas finitos no deterministas son dos tipos de "máquinas" conceptuales diseñados para comprobar si una determinada cadena de símbolos obedece a ciertas reglas - si es aceptable como un mensaje en un lenguaje o código . El autómata lee un símbolo a la vez, y siempre existe en un determinado " estado". Cada estado puede ser un autómata en cuenta con un conjunto de reglas para reaccionar a la siguiente símbolo para ser leído - que puede cambiar a otro estado particular , o siendo la misma . Si, después de una cadena entera ha sido leído , el autómata ha entrado en uno de un conjunto de estados finales aceptables " , " la cadena es gramaticalmente aceptables dentro del lenguaje de los autómatas está probando para . Instrucciones
1

Examinar las normas de la autómatas . Estos incluyen: . Todos los estados posibles de la autómatas, el conjunto de estados finales y los efectos de cada posible símbolo en cada estado
2

Comprobar para ver si alguno de los estados del autómatas tienen varias reacciones posibles a un símbolo particular . Si alguno lo hace , el autómata no es determinista - un NDFA . Por ejemplo , si el estado inicial de un autómata puede reaccionar con el símbolo " A" , ya sea por pasar a un segundo estado o al permanecer la misma , es una NDFA . Un NDFA devuelve un resultado positivo si hay alguna manera de llegar a un estado final con una cadena determinada .
3

tener en cuenta que existe un AFD para cada NDFA . Debido a que un NDFA devolver un resultado positivo para una cadena específica debe tener al menos un camino de éxito a través de ella para dicha cuerda , debe por necesidad ser un DFA correspondiente que acepte esa cadena , que contiene sólo las reglas para la trayectoria única que se utilizó . Aquí hay un ejemplo muy simple: Supongamos que usted tiene un NDFA con un estado final llamado S1 , cuyo estado inicial S0 responde al símbolo "A" ya sea cambiando a S1 o permaneciendo en S0. Esta máquina aceptaría una cadena que consiste simplemente en " A ", porque hay un camino posible a S1 , y hay un DFA correspondiente en el que "A" siempre cambia S1 S0 , prescindiendo de la ruta utilizada
.