1. DFA: DFA attiecas uz deterministisko galīgo automātu. Tiek uzskatīts, ka galīgais automāts (FA) ir deterministisks, ja tas atbilst ievades simbolam, ir viens rezultējošais stāvoklis, t.i., ir tikai viena pāreja. Deterministisks galīgs automāts ir piecu korešu kopa, kas attēlota kā,
kur,
J: Netukša ierobežota stāvokļu kopa ierobežotajā vadīklā (qo, q1, q2, …).
Σ: Netukša ierobežota ievades simbolu kopa.
δ: tā ir pārejas funkcija, kas izmanto divus argumentus, stāvokli un ievades simbolu, un tā atgriež vienu stāvokli.
qo: tas ir sākuma stāvoklis, viens no Q stāvokļiem.
F: Tā ir netukša gala stāvokļu kopa/pieņemšanas stāvokļu kopa no kopas, kas pieder Q.
2. CĒLOŅI:
NFA attiecas uz nondeterministisku galīgo automātu. Tiek uzskatīts, ka ierobežotais automāts (FA) ir nedeterministisks, ja vienā un tajā pašā ievades simbolā ir iespējama vairāk nekā viena pāreja no viena stāvokļa.
Nedeterminēts galīgs automāts ir arī piecu korešu kopa un attēlota kā,
kur,
J: Netukšu galīgo stāvokļu kopa.
Σ: Netukšu ierobežotu ievades simbolu kopa.
δ: tā ir pārejas funkcija, kas iegūst stāvokli no Q un ievades simbolu no un atgriež Q apakškopu.
qo: NFA sākotnējais stāvoklis un Q dalībnieks.
F: netukša gala stāvokļu kopa un Q dalībnieks.
Priekšnosacījums - Pabeigts automātiski
Atšķirība starp DFA un NFA:
| DFA | NFA |
|---|---|
| DFA apzīmē Deterministic Finite Automata. | NFA apzīmē Nondeterministic Finite Automata. |
| Katram simboliskajam alfabēta attēlojumam DFA ir tikai viena stāvokļa pāreja. | Nav jāprecizē, kā NFA reaģē pēc kāda simbola. |
| DFA nevar izmantot tukšas virknes pāreju. | NFA var izmantot tukšas virknes pāreju. |
| DFA var saprast kā vienu mašīnu. | NFA var saprast kā vairākas mazas mašīnas, kas skaitļo vienlaikus. |
| Programmā DFA nākamais iespējamais stāvoklis ir skaidri iestatīts. | NFA katram stāvokļa un ievades simbola pārim var būt daudz iespējamo nākamo stāvokļu. |
| DFA ir grūtāk izveidot. | NFA ir vieglāk izveidot. |
| DFA noraida virkni, ja tā beidzas stāvoklī, kas atšķiras no pieņemšanas stāvokļa. | NFA noraida virkni, ja visas filiāles mirst vai atsakās no virknes. |
| Ievades virknes izpildei nepieciešamais laiks ir mazāks. | Ievades virknes izpildei nepieciešams vairāk laika. |
| Visi DFA ir NFA. | Ne visas NFA ir DFA. |
| DFA ir nepieciešams vairāk vietas. | NFA prasa mazāk vietas nekā DFA. |
| Dead konfigurācija nav atļauta. piemēram: ja mēs dodam ievadi kā 0 q0 stāvoklī, tad mums ir jādod 1 kā ievade q0 kā pašcilpa. | Dead konfigurācija ir atļauta. piemēram: ja mēs dodam ievadi kā 0 q0 stāvoklī, lai mēs varētu dot nākamo ievadi 1 uz q1, kas pāriet uz nākamo stāvokli. |
| δ: QxΣ -> Q, t.i., nākamais iespējamais stāvoklis pieder Q. | δ: Qx(Σ U ε) -> 2^Q, t.i., nākamais iespējamais stāvoklis pieder Q jaudu kopai. |
| DFA ir atļauta atkāpšanās. | NFA ne vienmēr ir iespējama atkāpšanās. |
| Regulārās izteiksmes konvertēšana uz DFA ir sarežģīta. | Regulārās izteiksmes konvertēšana uz NFA ir vienkāršāka salīdzinājumā ar DFA. |
| Epsilon pārvietošana nav atļauta DFA | Epsilon kustība ir atļauta NFA |
| DFA pieļauj tikai vienu kustību vienai ievades alfabētam. | Viena ievades alfabētam var būt izvēle (vairāk nekā viena kustība). |