1. DFA: DFA viittaa deterministiseen äärelliseen automaatioon. Äärillisen automaatin (FA) sanotaan olevan deterministinen, jos se vastaa syötesymbolia, siinä on yksi resultanttitila, eli siinä on vain yksi siirtymä. Deterministinen äärellinen automaatti koostuu viidestä monikosta, jotka esitetään muodossa
Missä,
K: Ei-tyhjä äärellinen joukko tiloja äärellisessä ohjauksessa (qo, q1, q2, …).
Σ: Ei-tyhjä äärellinen joukko syöttösymboleita.
δ: Se on siirtymäfunktio, joka ottaa kaksi argumenttia, tilan ja syöttösymbolin, ja se palauttaa yhden tilan.
qo: Se on aloitustila, yksi Q:n tiloista.
F: Se on ei-tyhjä joukko lopputiloja/hyväksyviä tiloja Q:lle kuuluvasta joukosta.
2. SYYT:
NFA viittaa epädeterministiseen äärelliseen automaatioon. Äärillisen automaatin (FA) sanotaan olevan ei-deterministinen, jos samalla tulosymbolilla on useampi kuin yksi mahdollinen siirtymä yhdestä tilasta.
Epädeterministinen äärellinen automaatti on myös viiden monikon joukko ja se esitetään muodossa
Missä,
K: Joukko ei-tyhjiä äärellisiä tiloja.
Σ: Joukko ei-tyhjiä äärellisiä syötesymboleja.
δ: Se on siirtymäfunktio, joka ottaa tilan Q:sta ja syötesymbolin Q:sta ja palauttaa Q:n osajoukon.
qo: NFA:n alkutila ja Q:n jäsen.
F: Ei-tyhjä lopullisten tilojen joukko ja Q:n jäsen.
Edellytys - Valmis automaattinen
Ero DFA:n ja NFA:n välillä:
| DFA | NFA |
|---|---|
| DFA on lyhenne sanoista Deterministic Finite Automata. | NFA on lyhenne sanoista Nondeterministic Finite Automata. |
| Jokaiselle aakkosten symboliselle esitykselle on DFA:ssa vain yksi tilasiirtymä. | Ei tarvitse määritellä, miten NFA reagoi jonkin symbolin mukaan. |
| DFA ei voi käyttää Empty String -siirtymää. | NFA voi käyttää Empty String -siirtymää. |
| DFA voidaan ymmärtää yhdeksi koneeksi. | NFA voidaan ymmärtää useaksi pieneksi tietokoneeksi, jotka laskevat samanaikaisesti. |
| DFA:ssa seuraava mahdollinen tila on asetettu selvästi. | NFA:ssa jokaisella tila- ja tulosymboliparilla voi olla useita mahdollisia seuraavia tiloja. |
| DFA:ta on vaikeampi rakentaa. | NFA on helpompi rakentaa. |
| DFA hylkää merkkijonon, jos se päättyy tilaan, joka eroaa hyväksymistilasta. | NFA hylkää merkkijonon, jos kaikki haarat kuolevat tai hylkäävät merkkijonon. |
| Syöttömerkkijonon suorittamiseen tarvittava aika on vähemmän. | Syöttömerkkijonon suorittamiseen tarvittava aika on enemmän. |
| Kaikki DFA:t ovat NFA:ta. | Kaikki NFA:t eivät ole DFA:ta. |
| DFA vaatii enemmän tilaa. | NFA vaatii vähemmän tilaa kuin DFA. |
| Kuollut konfigurointi ei ole sallittu. esim.: jos annamme syötteen 0 q0-tilassa, niin meidän on annettava 1 syötteenä q0:lle itsesilmukana. | Kuollut konfigurointi on sallittu. esim.: jos annamme syötteen 0 q0-tilassa, jotta voimme antaa seuraavan syötteen 1 q1:lle, joka siirtyy seuraavaan tilaan. |
| δ: QxΣ -> Q eli seuraava mahdollinen tila kuuluu Q:lle. | δ: Qx(Σ U ε) -> 2^Q eli seuraava mahdollinen tila kuuluu Q:n tehojoukkoon. |
| Peruutus on sallittu DFA:ssa. | NFA:ssa perääntyminen ei ole aina mahdollista. |
| Säännöllisen lausekkeen muuntaminen DFA:ksi on vaikeaa. | Säännöllisen lausekkeen muuntaminen NFA:ksi on yksinkertaisempaa kuin DFA. |
| Epsilonin siirto ei ole sallittu DFA:ssa | Epsilonin siirto on sallittu NFA:ssa |
| DFA sallii vain yhden liikkeen yksittäistä syöteaakkosta varten. | Yksittäissyöttöaakkosille voi valita (useampi kuin yksi liike). |