• Az NFA a nem-determinisztikus véges automaták rövidítése. Egy adott reguláris nyelvhez egyszerűbb NFA-t létrehozni, mint DFA-t.
• A véges automatákat NFA-nak nevezzük, ha sok útvonal létezik az adott bemenethez az aktuális állapotból a következő állapotba.
• Minden NFA nem DFA, de mindegyik NFA lefordítható DFA-ra.
• Az NFA meghatározása ugyanúgy történik, mint a DFA, de a következő két kivétellel több következő állapotot tartalmaz, és ε átmenetet is tartalmaz.

A következő képen láthatjuk, hogy a q0 állapotból az a bemenetnél van két következő állapot: q1 és q2, hasonlóan, a q0-tól a b bemenethez a következő állapotok a q0 és q1. Így nem rögzített vagy meghatározott, hogy egy adott bemenettel merre tovább. Ezért ezt az FA-t nem-determinisztikus véges automatáknak nevezzük.

Az NFA hivatalos meghatározása:

Az NFA-nak is van öt állapota, amely megegyezik a DFA-val, de eltérő átmeneti funkcióval, az alábbiak szerint:

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

ahol,

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

Egy NFA grafikus ábrázolása

Az NFA-t állapotdiagramnak nevezett digráfokkal ábrázolhatjuk. Amiben:

1. Az állapotot csúcsok képviselik.
2. A bemeneti karakterrel jelölt ív mutatja az átmeneteket.
3. A kezdeti állapotot nyíl jelzi.
4. A végső állapotot a kettős kör jelöli.

1. példa:

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

Megoldás:

vacsora vs vacsoraidő

Átmeneti diagram:

Átmeneti táblázat:

A fenti ábrán láthatjuk, hogy amikor az aktuális állapot q0, akkor a 0 bemeneten a következő állapot q0 vagy q1, 1 bemeneten pedig q1 lesz. Ha az aktuális állapot q1, a 0 bemeneten a következő állapot q2, 1 bemeneten pedig a következő állapot q0. Ha az aktuális állapot q2, 0 bemeneten a következő állapot q2, 1 bemeneten pedig q1 vagy q2 lesz.

2. példa:

A ∑ = {0, 1} NFA minden 01-es karakterláncot elfogad.

Megoldás:

Átmeneti táblázat:

3. példa:

NFA ∑ = {0, 1} értékkel, és fogadjon el minden, legalább 2 hosszúságú karakterláncot.

Megoldás:

Átmeneti táblázat:

mysql listázza az összes felhasználót