• NFA står för icke-deterministiska finita automater. Det är lätt att konstruera en NFA än DFA för ett givet reguljärt språk.
• De finita automaterna kallas NFA när det finns många vägar för specifik inmatning från det aktuella tillståndet till nästa tillstånd.
• Varje NFA är inte DFA, men varje NFA kan översättas till DFA.
• NFA definieras på samma sätt som DFA men med följande två undantag innehåller den flera nästa tillstånd och den innehåller ε-övergång.

I följande bild kan vi se att från tillstånd q0 för ingång a, det finns två nästa tillstånd q1 och q2, på samma sätt, från q0 för ingång b, är nästa tillstånd q0 och q1. Det är alltså inte fixat eller bestämt att med en viss ingång vart man ska gå härnäst. Därför kallas denna FA icke-deterministiska finita automater.

Formell definition av NFA:

NFA har också fem tillstånd som är samma som DFA, men med olika övergångsfunktioner, enligt följande:

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

var,

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

Grafisk representation av en NFA

En NFA kan representeras av digrafer som kallas tillståndsdiagram. I vilken:

imessage-spel på Android

1. Staten representeras av hörn.
2. Bågen märkt med ett inmatningstecken visar övergångarna.
3. Det ursprungliga tillståndet är markerat med en pil.
4. Sluttillståndet betecknas med dubbelcirkeln.

Exempel 1:

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

Lösning:

Övergångsdiagram:

objektiv java

Övergångstabell:

I diagrammet ovan kan vi se att när det aktuella tillståndet är q0, på ingång 0, kommer nästa tillstånd att vara q0 eller q1, och på 1 ingång kommer nästa tillstånd att vara q1. När det aktuella tillståndet är q1 kommer nästa tillstånd på ingång 0 att vara q2 och på 1 ingång kommer nästa tillstånd att vara q0. När det aktuella tillståndet är q2, på 0-ingången är nästa tillstånd q2, och på 1-ingången kommer nästa tillstånd att vara q1 eller q2.

Exempel 2:

NFA med ∑ = {0, 1} accepterar alla strängar med 01.

Lösning:

avl träd

Övergångstabell:

Exempel 3:

NFA med ∑ = {0, 1} och acceptera alla strängar med minst 2 längder.

Lösning:

Övergångstabell: