• NFA pomeni nedeterministične končne avtomate. Za dani običajni jezik je enostavno sestaviti NFA kot DFA.
• Končni avtomati se imenujejo NFA, kadar obstaja veliko poti za določen vnos iz trenutnega stanja v naslednje stanje.
• Vsak NFA ni DFA, vendar je vsak NFA mogoče prevesti v DFA.
• NFA je definiran na enak način kot DFA, vendar z naslednjima dvema izjemama vsebuje več naslednjih stanj in vsebuje prehod ε.

Na naslednji sliki lahko vidimo, da iz stanja q0 za vhod a obstajata dve naslednji stanji q1 in q2, podobno sta iz q0 za vhod b naslednji stanji q0 in q1. Tako ni določeno ali določeno, kam iti naprej z določenim vnosom. Zato se ta FA imenuje nedeterministični končni avtomati.

Uradna definicija NFA:

NFA ima tudi pet enakih stanj kot DFA, vendar z drugačno prehodno funkcijo, kot je prikazano spodaj:

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

kje,

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

Grafični prikaz NFA

NFA je mogoče predstaviti z digrafi, imenovanimi diagrami stanja. V katerem:

1. Stanje je predstavljeno z vozlišči.
2. Lok, označen z vhodnim znakom, prikazuje prehode.
3. Začetno stanje je označeno s puščico.
4. Končno stanje je označeno z dvojnim krogom.

Primer 1:

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

rešitev:

Diagram prehoda:

Prehodna tabela:

V zgornjem diagramu lahko vidimo, da ko je trenutno stanje q0, bo na vhodu 0 naslednje stanje q0 ali q1, na vhodu 1 pa bo naslednje stanje q1. Ko je trenutno stanje q1, bo na vhodu 0 naslednje stanje q2 in na vhodu 1 bo naslednje stanje q0. Ko je trenutno stanje q2, je na vhodu 0 naslednje stanje q2, na vhodu 1 pa bo naslednje stanje q1 ali q2.

Primer 2:

NFA z ∑ = {0, 1} sprejme vse nize z 01.

rešitev:

Prehodna tabela:

Primer 3:

NFA z ∑ = {0, 1} in sprejme vse nize dolžine vsaj 2.

rešitev:

Prehodna tabela: