• NFA staat voor niet-deterministische eindige automaten. Het is gemakkelijk om een ​​NFA dan DFA te construeren voor een bepaalde reguliere taal.
• De eindige automaten worden NFA genoemd als er veel paden bestaan ​​voor specifieke invoer van de huidige staat naar de volgende staat.
• Elke NFA is geen DFA, maar elke NFA kan worden vertaald naar DFA.
• NFA wordt op dezelfde manier gedefinieerd als DFA, maar met de volgende twee uitzonderingen bevat het meerdere volgende toestanden en bevat het een ε-overgang.

In de volgende afbeelding kunnen we zien dat er vanaf toestand q0 voor ingang a twee volgende toestanden q1 en q2 zijn. Op dezelfde manier zijn vanaf q0 voor ingang b de volgende toestanden q0 en q1. Het ligt dus niet vast of bepaald dat met een bepaalde invoer waar naartoe moet. Daarom wordt deze FA niet-deterministische eindige automaten genoemd.

Formele definitie van NFA:

NFA heeft ook vijf toestanden die hetzelfde zijn als DFA, maar met een andere overgangsfunctie, zoals hieronder weergegeven:

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

waar,

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

Grafische weergave van een NFA

Een NFA kan worden weergegeven door digraphs, genaamd statusdiagram. Waarin:

ontkenning discrete wiskunde

1. De staat wordt weergegeven door hoekpunten.
2. De boog die is gelabeld met een invoerteken toont de overgangen.
3. De begintoestand is gemarkeerd met een pijl.
4. De eindtoestand wordt aangegeven door de dubbele cirkel.

Voorbeeld 1:

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

Oplossing:

Overgangsdiagram:

callback-hel in javascript

Overgangstabel:

In het bovenstaande diagram kunnen we zien dat wanneer de huidige toestand q0 is, op ingang 0 de volgende toestand q0 of q1 zal zijn, en op ingang 1 de volgende toestand q1 zal zijn. Wanneer de huidige toestand q1 is, zal op ingang 0 de volgende toestand q2 zijn en op ingang 1 zal de volgende toestand q0 zijn. Wanneer de huidige status q2 is, is bij ingang 0 de volgende status q2, en bij ingang 1 is de volgende status q1 of q2.

Voorbeeld 2:

NFA met ∑ = {0, 1} accepteert alle strings met 01.

Oplossing:

Hoe een string naar een int te converteren

Overgangstabel:

Voorbeeld 3:

NFA met ∑ = {0, 1} en accepteer alle strings met een lengte van minimaal 2.

Oplossing:

Overgangstabel: