• NFA significa autómata finito no determinista. Es más fácil construir un NFA que un DFA para un lenguaje regular determinado.
• Los autómatas finitos se denominan NFA cuando existen muchas rutas para entradas específicas desde el estado actual al siguiente.
• Cada NFA no es DFA, pero cada NFA se puede traducir a DFA.
• NFA se define de la misma manera que DFA, pero con las dos excepciones siguientes: contiene varios estados siguientes y contiene una transición ε.

En la siguiente imagen podemos ver que desde el estado q0 para la entrada a, hay dos estados siguientes q1 y q2, de manera similar, desde q0 para la entrada b, los siguientes estados son q0 y q1. Por lo tanto, no está fijado ni determinado con una entrada particular adónde ir a continuación. Por lo tanto, este FA se denomina autómata finito no determinista.

Definición formal de NFA:

NFA también tiene cinco estados iguales que DFA, pero con diferentes funciones de transición, como se muestra a continuación:

 &#x3B4;: Q x &#x2211; &#x2192;2<sup>Q</sup> 

dónde,

 Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function 

Representación gráfica de una NFA

Un NFA se puede representar mediante dígrafos llamados diagrama de estado. En el cual:

1. El estado está representado por vértices.
2. El arco etiquetado con un carácter de entrada muestra las transiciones.
3. El estado inicial está marcado con una flecha.
4. El estado final se indica con el doble círculo.

Ejemplo 1:

 Q = {q0, q1, q2} ∑ = {0, 1} q0 = {q0} F = {q2} 

Solución:

Diagrama de transición:

Tabla de transición:

En el diagrama anterior, podemos ver que cuando el estado actual es q0, en la entrada 0, el siguiente estado será q0 o q1, y en la entrada 1, el siguiente estado será q1. Cuando el estado actual es q1, en la entrada 0 el siguiente estado será q2 y en la entrada 1, el siguiente estado será q0. Cuando el estado actual es q2, en la entrada 0 el siguiente estado es q2, y en la entrada 1 el siguiente estado será q1 o q2.

Ejemplo 2:

NFA con ∑ = {0, 1} acepta todas las cadenas con 01.

Solución:

Tabla de transición:

Ejemplo 3:

NFA con ∑ = {0, 1} y acepta todas las cadenas de longitud al menos 2.

Solución:

Tabla de transición: