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
.