NFA i DFA

NFA vs DFA

Teorija računanja je grana računalne znanosti koja se bavi rješavanjem problema pomoću algoritama. Ima tri grane, naime; računalnu teoriju kompleksnosti, teoriju računanja i teoriju automata.

Automatska ili automatska teorija je proučavanje apstraktnih matematičkih strojeva ili sustava koji se mogu koristiti za rješavanje računalnih problema. Automat se sastoji od stanja i prijelaza, a kao što vidi simbol ili slovo ulaza, čini prijelaz na drugu državu, uzimajući trenutno stanje i simbol kao ulaz.

Automatska ili automatska teorija ima nekoliko klasa koje uključuju Deterministički konačni automati (DFA) i Nondeterministički konačni automati (NFA). Ove dvije klase su prijelazne funkcije automata ili automata.

U prijelazu DFA ne može upotrebljavati n prazan niz, a može se shvatiti kao jedan stroj. Ako niz završava u stanju koje nije prihvatljivo stanje, DFA će ga odbiti. DFA stroj može biti konstruiran sa svakim ulazom i izlazom.

DFA ima samo jednu državnu prijelaz za svaki simbol abecede, a postoji samo jedno konačno stanje za prijelaz, što znači da za svaki znak koji se čita, postoji jedna odgovarajuća država u DFA-i. Lakše je provjeriti članstvo u DFA-ju, ali je teško konstruirati. Povratak je dopušten u DFA-u i zahtijeva više prostora od NFA.

Backtracking nije uvijek dopušten u NFA. Iako je moguće u nekim slučajevima, u drugima to nije. Lakše je konstruirati NFA, a također zahtijeva manje prostora, ali nije moguće konstruirati NFA stroj za svaki ulaz i izlaz.

Podrazumijeva se kao nekoliko sitnih strojeva koji istodobno izračunavaju, a članstvo može biti teže provjeriti. Upotrebljava se Prazni nizni prijelaz, a postoje brojni mogući sljedeći stoji za svaki par država i ulaznog simbola. Pokreće se u određenoj državi i čita simbole, a automat tada određuje sljedeće stanje koje ovisi o trenutnom unosu i drugim posljedičnim događajima. U prihvatnom stanju, NFA prihvaća niz i odbacuje ga drugačije.

Sažetak:

1. "DFA" označava "Deterministički konačni automat" dok "NFA" označava "Nondeterministički konačni automata". 2.Sada su prijelazne funkcije automatskih. U DFA-i sljedeća moguća drzava je jasno postavljena, dok u NFA svaki par drzava i ulazni simbol moze imati mnogo mogucih sljedecih stanja. 3.NFA može koristiti prazan prijelaz niza dok DFA ne može upotrebljavati prazan prijelaz niza. 4.NFA je lakše konstruirati dok je teže konstruirati DFA. 5.Backtracking je dopuštena u DFA dok je u NFA-in svibanj ili svibanj ne biti dopušteno. 6.DFA zahtijeva više prostora, dok NFA zahtijeva manje prostora. 7. Dok se DFA može razumjeti kao jedan stroj i DFA stroj može biti konstruiran za svaki ulaz i izlaz, 8.NFA se može shvatiti kao nekoliko malih strojeva koji zajedno izračunavaju, a nema mogućnosti izgradnje NFA stroja za svaki unos i izlaz.