Ero NFA n ja DFA n välillä

NFA vs. DFA

Laskentateoria on tietotekniikan osa, joka käsittelee ongelmien ratkaisemista algoritmeilla. Sillä on kolme haaraa, nimittäin; laskennallisen monimutkaisusteorian, laskettavuuden teorian ja automaattiteorian.

Automaatti tai automaattiteoria on abstraktien matemaattisten koneiden tai järjestelmien tutkimus, joita voidaan käyttää ratkaisemaan laskennallisia ongelmia. Automaatti koostuu tiloista ja siirtymistä, ja koska se näkee syöttösymbolin tai kirjaimen, se siirtyy toiseen tilaan ottaen nykyisen tilan ja symbolin syötteeksi.

Automaatissa tai automaattiteoriassa on useita luokkia, joihin kuuluvat deterministiset äärelliset automaatit (DFA) ja epädeterministiset äärelliset automaatit (NFA). Nämä kaksi luokkaa ovat automaattien tai automaattien siirtymäfunktioita.

Siirtymävaiheessa DFA ei voi käyttää n tyhjää merkkijonoa, ja se voidaan ymmärtää yhdeksi koneeksi. Jos merkkijono päättyy tilaan, joka ei ole hyväksyttävä, DFA hylkää sen. DFA-kone voidaan rakentaa jokaisella tulolla ja ulostulolla.

DFA: lla on vain yksi tilamuutos aakkosten jokaiselle symbolille, ja sen siirtymiselle on vain yksi lopullinen tila, mikä tarkoittaa, että jokaisella luetulla merkillä DFA: ssa on yksi vastaava tila. DFA-jäsenyyden tarkistaminen on helpompaa, mutta sen rakentaminen on vaikeampaa. Jäljitys on sallittu DFA: ssa, ja se vaatii enemmän tilaa kuin NFA.

Takaisinotto ei ole aina sallittua NFA: ssa. Vaikka joissakin tapauksissa se on mahdollista, toisissa se ei ole. NFA: n rakentaminen on helpompaa, ja se vie myös vähemmän tilaa, mutta NFA-konetta ei voida rakentaa jokaiselle tulolle ja ulostulolle.

Se ymmärretään useiksi pieniksi koneiksi, jotka laskevat samanaikaisesti, ja jäsenyyttä voi olla vaikeampi tarkistaa. Se käyttää tyhjää merkkijonomuutosta, ja jokaiselle tila- ja syöttösymboliparille on useita mahdollisia seuraavia tiloja. Se alkaa tietystä tilasta ja lukee symbolit, ja automaatti määrittää sitten seuraavan tilan, joka riippuu nykyisestä tulosta ja muista seuraavista tapahtumista. Hyväksymistilassaan NFA hyväksyy merkkijonon ja hylkää sen muuten.

Yhteenveto:

1. "DFA" tarkoittaa "determinististä äärellistä automaattia" ja "NFA" tarkoittaa "epädeterminististä äärellistä automaattia".
2.Eivät molemmat ole automaattien siirtymäfunktioita. DFA: ssa seuraava mahdollinen tila asetetaan selvästi, kun taas NFA: lla jokaisella tila- ja sisääntulo-parilla voi olla monia mahdollisia seuraavia tiloja.
3.NFA voi käyttää tyhjää merkkijononsiirtoa, kun taas DFA ei voi käyttää tyhjää merkkijonomuutosta.
4.NFA: n rakentaminen on helpompaa, kun taas DFA: n rakentaminen on vaikeampaa.
5.Takaisinseuranta on sallittu DFA: ssa, kun taas NFA: ssa se voi olla tai ei ole sallittua.
6.DFA vaatii enemmän tilaa, kun taas NFA vaatii vähemmän tilaa.
7.Jos DFA voidaan ymmärtää yhdeksi koneeksi ja DFA-kone voidaan rakentaa jokaiselle tulolle ja ulostulolle, 8.NFA voidaan ymmärtää useaksi pieneksi koneeksi, jotka laskevat yhdessä, eikä NFA-konetta ole mahdollista rakentaa jokaiselle tulolle ja lähtö.