1. DFA: DFA označuje deterministický konečný automat. O konečném automatu (FA) se říká, že je deterministický, pokud odpovídá vstupnímu symbolu, existuje jediný výsledný stav, tj. existuje pouze jeden přechod. Deterministický konečný automat je množina pěti n-tic reprezentovaných jako,
Kde,
Q: Neprázdná konečná množina stavů v konečné kontrole (qo, q1, q2, …).
Σ: Neprázdná konečná množina vstupních symbolů.
δ: Je to přechodová funkce, která přebírá dva argumenty, stav a vstupní symbol, vrací jeden stav.
qo: Je to počáteční stav, jeden ze stavů v Q.
F: Je to neprázdná množina konečných stavů/přijímajících stavů z množiny patřící do Q.
2. PŘÍČINY:
NFA označuje nedeterministický konečný automat. Konečný automat (FA) je považován za nedeterministický, pokud existuje více než jeden možný přechod z jednoho stavu na stejném vstupním symbolu.
Nedeterministický konečný automat je také množina pěti n-tic a je reprezentována jako,
Kde,
Q: Množina neprázdných konečných stavů.
Σ: Sada neprázdných konečných vstupních symbolů.
δ: Je to přechodová funkce, která přebírá stav z Q a vstupní symbol z a vrací podmnožinu Q.
qo: Počáteční stav NFA a člen Q.
F: Neprázdný soubor konečných stavů a člen Q.
Předpoklad - Hotovo automaticky
Rozdíl mezi DFA a NFA:
| DFA | NFA |
|---|---|
| DFA je zkratka pro Deterministic Finite Automata. | NFA je zkratka pro nedeterministické konečné automaty. |
| Pro každou symbolickou reprezentaci abecedy existuje v DFA pouze jeden přechod stavu. | Není třeba specifikovat, jak NFA reaguje podle nějakého symbolu. |
| DFA nemůže použít přechod Prázdný řetězec. | NFA může použít přechod Empty String. |
| DFA lze chápat jako jeden stroj. | NFA lze chápat jako několik malých strojů pracujících současně. |
| V DFA je zřetelně nastaven další možný stav. | V NFA může mít každá dvojice stavu a vstupního symbolu mnoho možných dalších stavů. |
| Konstrukce DFA je obtížnější. | NFA je jednodušší na konstrukci. |
| DFA odmítne řetězec v případě, že skončí ve stavu, který se liší od stavu přijímajícího. | NFA odmítne řetězec v případě, že všechny větve zemřou nebo řetězec odmítnou. |
| Čas potřebný k provedení vstupního řetězce je kratší. | Čas potřebný k provedení vstupního řetězce je delší. |
| Všechny DFA jsou NFA. | Ne všechny NFA jsou DFA. |
| DFA vyžaduje více místa. | NFA vyžaduje méně místa než DFA. |
| Mrtvá konfigurace není povolena. např.: pokud dáme vstup jako 0 ve stavu q0, musíme dát 1 jako vstup do q0 jako vlastní smyčku. | Mrtvá konfigurace je povolena. např.: pokud dáme vstup jako 0 na q0 stavu, takže můžeme dát další vstup 1 na q1, který přejde do dalšího stavu. |
| δ: QxΣ -> Q tj. další možný stav patří do Q. | δ: Qx(Σ U ε) -> 2^Q tj. další možný stav patří do mocniny Q. |
| Zpětné sledování je ve službě DFA povoleno. | Zpětné sledování není v NFA vždy možné. |
| Převod regulárního výrazu do DFA je obtížný. | Převod regulárního výrazu na NFA je ve srovnání s DFA jednodušší. |
| Přesun Epsilon není ve službě DFA povolen | Epsilonový pohyb je v NFA povolen |
| DFA umožňuje pouze jeden tah pro jednu vstupní abecedu. | Může být na výběr (více než jeden tah) pro jednu vstupní abecedu. |