1. DFA: DFA označuje deterministický konečný automat. Konečný automat (FA) sa považuje za deterministický, ak zodpovedá vstupnému symbolu, existuje jediný výsledný stav, t. j. existuje len jeden prechod. Deterministický konečný automat je množina piatich n-tic reprezentovaných ako,
Kde,
Q: Neprázdna konečná množina stavov v konečnej kontrole (qo, q1, q2, ...).
Σ: Neprázdna konečná množina vstupných symbolov.
δ: Je to prechodová funkcia, ktorá má dva argumenty, stav a vstupný symbol, vracia jeden stav.
qo: Je to počiatočný stav, jeden zo stavov v Q.
F: Je to neprázdna množina konečných stavov/akceptujúcich stavov z množiny patriacej do Q.
2. PRÍČINY:
NFA označuje nedeterministický konečný automat. Konečný automat (FA) sa považuje za nedeterministický, ak existuje viac ako jeden možný prechod z jedného stavu na rovnakom vstupnom symbole.
Nedeterministický konečný automat je tiež množina piatich n-tic a je reprezentovaná ako,
Kde,
Otázka: Množina neprázdnych konečných stavov.
Σ: Množina neprázdnych konečných vstupných symbolov.
δ: Je to prechodová funkcia, ktorá preberá stav z Q a vstupný symbol z a vracia podmnožinu Q.
qo: Počiatočný stav NFA a člen Q.
F: Neprázdny súbor konečných štátov a člen Q.
Predpoklad - Dokončené automaticky
Rozdiel medzi DFA a NFA:
| DFA | NFA |
|---|---|
| DFA je skratka pre Deterministic Finite Automata. | NFA znamená nedeterministické konečné automaty. |
| Pre každú symbolickú reprezentáciu abecedy existuje v DFA iba jeden prechod stavu. | Netreba špecifikovať, ako NFA reaguje podľa nejakého symbolu. |
| Služba DFA nemôže použiť prechod Prázdny reťazec. | NFA môže použiť prechod Empty String. |
| DFA možno chápať ako jeden stroj. | NFA možno chápať ako viacero malých strojov počítajúcich súčasne. |
| V DFA je zreteľne nastavený ďalší možný stav. | V NFA môže mať každý pár stavov a vstupných symbolov mnoho možných ďalších stavov. |
| Konštrukcia DFA je náročnejšia. | NFA je jednoduchšie zostaviť. |
| DFA odmietne reťazec v prípade, že sa skončí v inom stave, ako je stav prijímania. | NFA odmietne reťazec v prípade, že všetky pobočky zomrú alebo odmietnu reťazec. |
| Čas potrebný na vykonanie vstupného reťazca je kratší. | Čas potrebný na vykonanie vstupného reťazca je dlhší. |
| Všetky DFA sú NFA. | Nie všetky NFA sú DFA. |
| DFA vyžaduje viac miesta. | NFA vyžaduje menej miesta ako DFA. |
| Mŕtva konfigurácia nie je povolená. napr.: ak dáme vstup ako 0 v stave q0, tak musíme dať 1 ako vstup do q0 ako vlastnú slučku. | Mŕtva konfigurácia je povolená. napr.: ak dáme vstup ako 0 na q0 stave, tak môžeme dať ďalší vstup 1 na q1, ktorý prejde do ďalšieho stavu. |
| δ: QxΣ -> Q t.j. ďalší možný stav patrí do Q. | δ: Qx(Σ U ε) -> 2^Q t.j. ďalší možný stav patrí do mocninovej množiny Q. |
| Spätné sledovanie je v službe DFA povolené. | Backtracking nie je v NFA vždy možný. |
| Konverzia regulárneho výrazu na DFA je náročná. | Konverzia regulárneho výrazu na NFA je v porovnaní s DFA jednoduchšia. |
| Epsilon presun nie je povolený v DFA | Epsilonový pohyb je povolený v NFA |
| Služba DFA umožňuje iba jeden pohyb pre abecedu s jedným vstupom. | Existuje možnosť výberu (viac ako jeden ťah) pre jednu vstupnú abecedu. |