1. DFA: DFA reiškia deterministinį baigtinį automatą. Sakoma, kad baigtinis automatas (FA) yra deterministinis, jei atitinka įvesties simbolį, yra viena gaunama būsena, ty yra tik vienas perėjimas. Deterministinis baigtinis automatas yra penkių eilučių rinkinys, vaizduojamas kaip
kur,
K: Netuščia baigtinė būsenų rinkinys baigtiniame valdiklyje (qo, q1, q2, …).
Σ: netuščias baigtinis įvesties simbolių rinkinys.
δ: tai perėjimo funkcija, kuriai reikia dviejų argumentų, būsenos ir įvesties simbolio, ji grąžina vieną būseną.
qo: tai pradinė būsena, viena iš Q būsenų.
F: Tai netuščias galutinių būsenų rinkinys / priėmimo būsenos iš rinkinio, priklausančio Q.
2. PRIEŽASTYS:
NFA reiškia nedeterministinį baigtinį automatą. Laikoma, kad baigtinis automatas (FA) yra nedeterministinis, jei tame pačiame įvesties simbolyje yra daugiau nei vienas galimas perėjimas iš vienos būsenos.
Nedeterministinis baigtinis automatas taip pat yra penkių eilučių rinkinys ir vaizduojamas kaip,
kur,
K: Netuščių baigtinių būsenų rinkinys.
Σ: netuščių baigtinių įvesties simbolių rinkinys.
δ: tai perėjimo funkcija, kuri perima būseną iš Q ir įvesties simbolį iš Q poaibį ir grąžina jį.
qo: pradinė NFA būsena ir Q narys.
F: netuščias galutinių būsenų rinkinys ir Q narys.
Būtina sąlyga – Užbaigtas automatinis
Skirtumas tarp DFA ir NFA:
| DFA | NFA |
|---|---|
| DFA reiškia deterministinius baigtinius automatus. | NFA reiškia Nondeterministic Finite Automata. |
| Kiekvienam simboliniam abėcėlės vaizdavimui DFA yra tik vienas būsenos perėjimas. | Nereikia nurodyti, kaip NFA reaguoja pagal kažkokį simbolį. |
| DFA negali naudoti tuščios eilutės perėjimo. | NFA gali naudoti „Empty String“ perėjimą. |
| DFA galima suprasti kaip vieną mašiną. | NFA gali būti suprantama kaip kelios mažos mašinos, skaičiuojančios vienu metu. |
| DFA kita galima būsena yra aiškiai nustatyta. | NFA kiekviena būsenos ir įvesties simbolio pora gali turėti daug galimų kitų būsenų. |
| DFA sukurti sunkiau. | NFA lengviau sukurti. |
| DFA atmeta eilutę, jei ji baigiasi būsena, kuri skiriasi nuo priėmimo būsenos. | NFA atmeta eilutę, jei visos šakos miršta arba jos atsisakoma. |
| Įvesties eilutės vykdymui reikalingas laikas yra trumpesnis. | Įvesties eilutės vykdymui reikia daugiau laiko. |
| Visi DFA yra NFA. | Ne visos NFA yra DFA. |
| DFA reikia daugiau vietos. | NFA reikalauja mažiau vietos nei DFA. |
| Neveikianti konfigūracija neleidžiama. pvz.: jei q0 būsenoje įvestį pateikiame kaip 0, tai q0 kaip savaiminę kilpą turime suteikti 1 kaip įvestį. | Leidžiama neveikianti konfigūracija. pvz.: jei duosime įvestį kaip 0 q0 būsenoje, tai galime duoti kitą įvestį 1 q1, kuri pereis į kitą būseną. |
| δ: QxΣ -> Q, ty kita galima būsena priklauso Q. | δ: Qx(Σ U ε) -> 2^Q, ty kita galima būsena priklauso Q galių rinkiniui. |
| DFA leidžiama grįžti atgal. | NFA ne visada įmanoma grįžti atgal. |
| Reguliariąją išraišką konvertuoti į DFA sunku. | Reguliariosios išraiškos konvertavimas į NFA yra paprastesnis, palyginti su DFA. |
| Epsilon judėjimas neleidžiamas DFA | Epsilon judėjimas leidžiamas NFA |
| DFA leidžia tik vieną judesį naudojant vieną įvesties abėcėlę. | Galima pasirinkti (daugiau nei vieną judesį) vienai įvesties abėcėlę. |