Razlika između NFA i DFA

NFA vs DFA

Teorija računanja je grana informatike koja se bavi načinom na koji se problemi rješavaju pomoću algoritama. Ima tri grane, naime; teorija složenosti računanja, teorija izračuna i teorija automata.

Teorija automata ili automata je proučavanje apstraktnih matematičkih strojeva ili sustava koji se mogu koristiti za rješavanje računarskih problema. Automatizam se sastoji od stanja i prijelaza, a kako vidi simbol ili slovo unosa, prelazi u drugo stanje uzimajući trenutno stanje i simbol kao ulaz.

Teorija automata ili automata ima nekoliko klasa koje uključuju determinirane konačne automete (DFA) i nedeterministrativni konačni automati (NFA). Ove su dvije klase prijelazne funkcije automata ili automata.

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

DFA ima samo jedan prijelaz stanja za svaki simbol abecede, a postoji samo jedno konačno stanje za njegov prijelaz, što znači da za svaki lik koji se čita, postoji jedno odgovarajuće stanje u DFA. Lakše je provjeriti članstvo u DFA-i, ali teže je konstruirati. Potražnja je dopuštena u DFA-u i zahtijeva više prostora od NFA.

Povlačenje unatrag nije uvijek dopušteno u NFA. U nekim je slučajevima moguće, u drugim nije. Lakše je konstruirati NFA, a zahtijeva i manje prostora, ali nije moguće konstruirati NFA stroj za svaki ulaz i izlaz.

To se podrazumijeva kao nekoliko malenih strojeva koji se računaju istovremeno, a članstvo se može i teže provjeriti. Koristi Prijelaz praznog niza i postoje brojne moguće sljedeće države za svaki par stanja i simbola unosa. Ona započinje u određenom stanju i čita simbole, a automat zatim određuje sljedeće stanje koje ovisi o trenutnom ulazu i ostalim posljedičnim događajima. U svom prihvaćenom stanju, NFA prihvaća string i odbacuje ga na drugi način.

Sažetak:

1. "DFA" označava "Deterministički konačni automati", dok "NFA" označava "Neodređeni konačni automati."
2.Bok su prijelazne funkcije automata. U DFA je sljedeće moguće stanje jasno postavljeno, dok u NFA svaki par stanja i ulazni simbol mogu imati više mogućih sljedećih stanja.
3.NFA može koristiti prijelaz praznog niza dok DFA ne može koristiti prijelaz prazni niz.
4.NFA je lakše konstruirati dok je teže konstruirati DFA.
5.Backtracking je dopušteno u DFA-u, dok je u NFA-u to može ili ne mora biti dopušteno.
6.DFA zahtijeva više prostora dok NFA zahtijeva manje prostora.
7. Dok se DFA može shvatiti kao jedan stroj i DFA stroj može se konstruirati za svaki ulaz i izlaz, 8.NFA se može razumjeti kao nekoliko malih strojeva koji se međusobno računaju i ne postoji mogućnost konstrukcije NFA stroja za svaki ulaz i izlaz.