1. DFA: DFA se nanaša na deterministični končni avtomat. Za končni avtomat (FA) pravimo, da je determinističen, če ustreza vhodnemu simbolu, obstaja eno samo rezultantno stanje, tj. obstaja samo en prehod. Deterministični končni avtomat je niz petih tuplov, predstavljenih kot
Kje,
V: Neprazna končna množica stanj v končnem nadzoru (qo, q1, q2, …).
Σ: Neprazna končna množica vhodnih simbolov.
δ: Je prehodna funkcija, ki sprejme dva argumenta, stanje in vhodni simbol, vrne eno samo stanje.
qo: Je začetno stanje, eno od stanj v Q.
F: Je neprazna množica končnih stanj/sprejemljivih stanj iz množice, ki pripada Q.
2. VZROKI:
NFA se nanaša na nedeterministični končni avtomat. Končni avtomat (FA) naj bi bil nedeterminističen, če obstaja več kot en možen prehod iz enega stanja na isti vhodni simbol.
Nedeterministični končni avtomati so tudi nabor petih tulp in predstavljeni kot,
Kje,
V: Niz nepraznih končnih stanj.
Σ: Niz nepraznih končnih vhodnih simbolov.
δ: Je prehodna funkcija, ki vzame stanje iz Q in vhodni simbol iz ter vrne podmnožico Q.
qo: Začetno stanje NFA in član Q.
F: Neprazna množica končnih stanj in član Q.
Predpogoj – Končano samodejno
Razlika med DFA in NFA:
| DFA | NFA |
|---|---|
| DFA je kratica za Deterministic Finite Automata. | NFA je kratica za Nondeterministic Finite Automata. |
| Za vsako simbolno predstavitev abecede obstaja samo en prehod stanja v DFA. | Ni treba navajati, kako se NFA odzove glede na neki simbol. |
| DFA ne more uporabiti prehoda prazen niz. | NFA lahko uporablja prehod prazen niz. |
| DFA lahko razumemo kot en stroj. | NFA lahko razumemo kot več majhnih strojev, ki računajo hkrati. |
| V DFA je naslednje možno stanje jasno določeno. | V NFA ima lahko vsak par stanja in vhodnega simbola veliko možnih naslednjih stanj. |
| DFA je težje zgraditi. | NFA je lažje zgraditi. |
| DFA zavrne niz, če se konča v stanju, ki je drugačno od stanja sprejema. | NFA zavrne niz v primeru, da vse veje odmrejo ali zavrnejo niz. |
| Čas, potreben za izvedbo vhodnega niza, je manjši. | Čas, potreben za izvedbo vhodnega niza, je daljši. |
| Vsi DFA so NFA. | Niso vsi NFA DFA. |
| DFA zahteva več prostora. | NFA zahteva manj prostora kot DFA. |
| Mrtva konfiguracija ni dovoljena. npr.: če podamo vhod kot 0 v stanju q0, moramo dati 1 kot vhod v q0 kot samozanko. | Dovoljena je mrtva konfiguracija. npr.: če podamo vnos kot 0 v stanju q0, tako lahko damo naslednji vnos 1 v q1, ki bo šel v naslednje stanje. |
| δ: QxΣ -> Q tj. naslednje možno stanje pripada Q. | δ: Qx(Σ U ε) -> 2^Q tj. naslednje možno stanje pripada potenčnemu nizu Q. |
| V DFA je dovoljeno sledenje nazaj. | Sledenje nazaj ni vedno mogoče v NFA. |
| Pretvorba regularnega izraza v DFA je težavna. | Pretvorba regularnega izraza v NFA je preprostejša v primerjavi z DFA. |
| Epsilon premik ni dovoljen v DFA | Premik Epsilon je dovoljen v NFA |
| DFA dovoljuje samo eno potezo za eno abecedo vnosa. | Obstaja možnost izbire (več kot ena poteza) za eno abecedo vnosa. |