TechCodeview

• NFA je kratica za nedeterminističke konačne automate. Lako je konstruirati NFA nego DFA za dati uobičajeni jezik.
• Konačni automati nazivaju se NFA kada postoji mnogo putova za određeni unos iz trenutnog stanja u sljedeće stanje.
• Svaki NFA nije DFA, ali se svaki NFA može prevesti u DFA.
• NFA je definiran na isti način kao i DFA, ali uz sljedeće dvije iznimke, sadrži više sljedećih stanja i sadrži ε prijelaz.

Na sljedećoj slici možemo vidjeti da od stanja q0 za ulaz a, postoje dva sljedeća stanja q1 i q2, slično tome, od q0 za ulaz b, sljedeća stanja su q0 i q1. Stoga nije fiksno niti određeno da s određenim unosom kamo ići dalje. Stoga se ovaj FA naziva nedeterminističkim konačnim automatima.

Formalna definicija NFA:

NFA također ima pet stanja istih kao DFA, ali s drugačijom prijelaznom funkcijom, kao što je prikazano u nastavku:

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

gdje,

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

Grafički prikaz NFA

NFA se može prikazati digrafovima koji se nazivaju dijagrami stanja. U kojem:

1. Stanje je predstavljeno vrhovima.
2. Luk označen ulaznim znakom prikazuje prijelaze.
3. Početno stanje je označeno strelicom.
4. Konačno stanje je označeno dvostrukim krugom.

Primjer 1:

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

Riješenje:

Prijelazni dijagram:

Prijelazna tablica:

Na gornjem dijagramu možemo vidjeti da kada je trenutno stanje q0, na ulazu 0, sljedeće stanje će biti q0 ili q1, a na 1 ulazu sljedeće stanje će biti q1. Kada je trenutno stanje q1, na ulazu 0 sljedeće stanje će biti q2, a na ulazu 1 sljedeće stanje će biti q0. Kada je trenutno stanje q2, na ulazu 0 sljedeće stanje je q2, a na ulazu 1 sljedeće stanje će biti q1 ili q2.

Primjer 2:

NFA s ∑ = {0, 1} prihvaća sve nizove s 01.

Riješenje:

Prijelazna tablica:

Primjer 3:

NFA s ∑ = {0, 1} i prihvaća sve nizove duljine najmanje 2.

Riješenje:

Prijelazna tablica: