• NFA står for ikke-deterministiske endelige automater. Det er enkelt å konstruere en NFA enn DFA for et gitt vanlig språk.
• De endelige automatene kalles NFA når det finnes mange veier for spesifikke input fra gjeldende tilstand til neste tilstand.
• Hver NFA er ikke DFA, men hver NFA kan oversettes til DFA.
• NFA er definert på samme måte som DFA, men med følgende to unntak, inneholder den flere neste tilstander, og den inneholder ε-overgang.

I det følgende bildet kan vi se at fra tilstand q0 for inngang a, er det to neste tilstander q1 og q2, på samme måte, fra q0 for inngang b, er de neste tilstandene q0 og q1. Dermed er det ikke løst eller bestemt at med en bestemt inngang hvor du skal gå videre. Derfor kalles denne FA ikke-deterministiske endelige automater.

Formell definisjon av NFA:

NFA har også fem stater samme som DFA, men med annen overgangsfunksjon, som vist nedenfor:

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

hvor,

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

Grafisk representasjon av en NFA

En NFA kan representeres av digrafer kalt tilstandsdiagram. I hvilke:

1. Staten er representert ved hjørner.
2. Buen merket med et inndatategn viser overgangene.
3. Starttilstanden er markert med en pil.
4. Den endelige tilstanden er angitt med den doble sirkelen.

Eksempel 1:

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

Løsning:

Overgangsdiagram:

Overgangstabell:

I diagrammet ovenfor kan vi se at når gjeldende tilstand er q0, på inngang 0, vil neste tilstand være q0 eller q1, og på 1 inngang vil neste tilstand være q1. Når gjeldende tilstand er q1, på inngang 0 vil neste tilstand være q2 og på 1 inngang vil neste tilstand være q0. Når gjeldende tilstand er q2, på 0-inngang er neste tilstand q2, og på 1-inngang vil neste tilstand være q1 eller q2.

Eksempel 2:

NFA med ∑ = {0, 1} godtar alle strenger med 01.

Løsning:

legge til strenger java

Overgangstabell:

Eksempel 3:

NFA med ∑ = {0, 1} og godta alle strenger med lengde på minst 2.

Løsning:

Overgangstabell: