• NFA significa autòmats finits no deterministes. És fàcil construir un NFA que un DFA per a un llenguatge normal determinat.
• Els autòmats finits s'anomenen NFA quan hi ha molts camins per a una entrada específica des de l'estat actual fins al següent.
• Cada NFA no és DFA, però cada NFA es pot traduir a DFA.
• NFA es defineix de la mateixa manera que DFA, però amb les dues excepcions següents, conté diversos estats següents i conté transició ε.

A la imatge següent, podem veure que des de l'estat q0 per a l'entrada a, hi ha dos estats següents q1 i q2, de manera similar, des de q0 per a l'entrada b, els següents estats són q0 i q1. Per tant, no es fixa ni es determina que amb una entrada determinada cap a on s'ha d'anar a continuació. Per tant, aquest FA s'anomena autòmat finit no determinista.

Definició formal de NFA:

NFA també té cinc estats iguals que DFA, però amb una funció de transició diferent, tal com es mostra a continuació:

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

on,

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

Representació gràfica d'un NFA

Un NFA es pot representar mitjançant dígrafs anomenats diagrama d'estats. En quin:

1. L'estat es representa amb vèrtexs.
2. L'arc etiquetat amb un caràcter d'entrada mostra les transicions.
3. L'estat inicial està marcat amb una fletxa.
4. L'estat final es denota amb el doble cercle.

Exemple 1:

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

Solució:

Diagrama de transició:

Taula de transició:

Al diagrama anterior, podem veure que quan l'estat actual és q0, a l'entrada 0, el següent estat serà q0 o q1, i a l'entrada 1 el següent estat serà q1. Quan l'estat actual és q1, a l'entrada 0 el següent estat serà q2 i a l'entrada 1, el següent estat serà q0. Quan l'estat actual és q2, a l'entrada 0 el següent estat és q2 i a l'entrada 1 el següent estat serà q1 o q2.

Exemple 2:

NFA amb ∑ = {0, 1} accepta totes les cadenes amb 01.

Solució:

Taula de transició:

Exemple 3:

NFA amb ∑ = {0, 1} i accepta totes les cadenes de longitud com a mínim 2.

Solució:

Taula de transició: