• NFA znamená nedeterministické konečné automaty. Je ľahké vytvoriť NFA ako DFA pre daný bežný jazyk.
• Konečné automaty sa nazývajú NFA, keď existuje veľa ciest pre špecifický vstup z aktuálneho stavu do nasledujúceho stavu.
• Každý NFA nie je DFA, ale každý NFA môže byť preložený do DFA.
• NFA je definovaný rovnakým spôsobom ako DFA, ale s nasledujúcimi dvoma výnimkami obsahuje viacero ďalších stavov a obsahuje prechod ε.

Na nasledujúcom obrázku vidíme, že zo stavu q0 pre vstup a sú dva ďalšie stavy q1 a q2, podobne od q0 pre vstup b sú ďalšie stavy q0 a q1. Nie je teda pevne dané alebo určené, že s konkrétnym vstupom, kam ísť ďalej. Preto sa tento FA nazýva nedeterministické konečné automaty.

Formálna definícia NFA:

NFA má tiež päť stavov rovnakých ako DFA, ale s inou prechodovou funkciou, ako je uvedené nižšie:

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

kde,

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

Grafické znázornenie NFA

NFA môže byť reprezentovaný digrafmi nazývanými stavový diagram. V ktorom:

1. Stav je reprezentovaný vrcholmi.
2. Oblúk označený vstupným znakom zobrazuje prechody.
3. Počiatočný stav je označený šípkou.
4. Konečný stav je označený dvojitým kruhom.

Príklad 1:

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

Riešenie:

Schéma prechodu:

Prechodová tabuľka:

Vo vyššie uvedenom diagrame môžeme vidieť, že keď je aktuálny stav q0, na vstupe 0 bude nasledujúci stav q0 alebo q1 a na 1 vstupe bude nasledujúci stav q1. Keď je aktuálny stav q1, na vstupe 0 bude nasledujúci stav q2 a na vstupe 1 bude nasledujúci stav q0. Keď je aktuálny stav q2, na 0 vstupe je nasledujúci stav q2 a na 1 vstupe bude nasledujúci stav q1 alebo q2.

Príklad 2:

NFA s ∑ = {0, 1} akceptuje všetky reťazce s 01.

Riešenie:

Prechodová tabuľka:

Príklad 3:

NFA s ∑ = {0, 1} a akceptujte všetky reťazce s dĺžkou aspoň 2.

Riešenie:

Prechodová tabuľka: