Razlika med NFA in DFA

NFA proti DFA

Teorija računanja je veja računalništva, ki se ukvarja s tem, kako težave rešujemo z algoritmi. Ima tri veje, in sicer; teorijo kompleksnosti računa, teorijo računanja in teorijo avtomatikov.

Teorija avtomatov ali avtomatikov je preučevanje abstraktnih matematičnih strojev ali sistemov, ki jih lahko uporabimo za reševanje računskih problemov. Avtomat je sestavljen iz stanj in prehodov, in ko vidi simbol ali črko vnosa, naredi prehod v drugo stanje, pri čemer trenutno stanje in simbol vneseta.

Teorija avtomatov ali avtomatov ima več razredov, ki vključujejo determinirane končne avtomate (DFA) in nedeterminirane končne avtomate (NFA). Ta dva razreda sta prehodni funkciji avtomata ali avtomatika.

DFA pri prehodu ne more uporabiti n praznega niza in ga je mogoče razumeti kot en stroj. Če se niz konča v stanju, ki ni sprejemljivo, ga DFA zavrne. Z vsakim vhodom in izhodom lahko izdelamo stroj DFA.

DFA ima samo en prehod stanja za vsak simbol abecede, in obstaja samo eno končno stanje za njegov prehod, kar pomeni, da je za vsak znak, ki ga beremo, v DFA eno ustrezno stanje. Članstvo v DFA je lažje preveriti, vendar je težje sestaviti. Povratno sledenje je v DFA dovoljeno in zahteva več prostora kot NFA.

Povratno sledenje ni vedno dovoljeno v NFA. V nekaterih primerih je to mogoče, v drugih pa ne. Lažje je konstruirati NFA in zahteva tudi manj prostora, vendar ni mogoče zgraditi NFA stroja za vsak vhod in izhod.

Razume se kot več drobnih strojev, ki računajo hkrati, in članstvo je težje preveriti. Uporablja prehod praznih nizov in obstaja veliko možnih naslednjih stanj za vsak par stanj in vhodni simbol. Začne se v določenem stanju in prebere simbole, avtomatika nato določi naslednje stanje, ki je odvisno od trenutnega vnosa in drugih posledičnih dogodkov. NFA v sprejemnem stanju sprejme niz in ga drugače zavrne.

Povzetek:

1. "DFA" pomeni "Deterministični končni avtomati", medtem ko "NFA" pomeni "Nedodeljeni končni avtomati."
2.Both so funkcije prehoda avtomatov. V DFA je naslednje možno stanje jasno nastavljeno, medtem ko ima v NFA lahko vsak par stanj in vhodni simbol več možnih naslednjih stanj.
3.NFA lahko uporablja prehod praznega niza, medtem ko DFA ne more uporabiti prehoda praznega niza.
4.NFA je lažje sestaviti, medtem ko je DFA težje sestaviti.
5.Backtracking je dovoljeno v DFA, medtem ko je v NFA dovoljeno ali ne.
6.DFA zahteva več prostora, medtem ko NFA potrebuje manj prostora.
7.Če DFA lahko razumemo kot en stroj in DFA stroj lahko konstruiramo za vsak vhod in izhod, 8.NFA lahko razumemo kot več majhnih strojev, ki računajo skupaj, in ni možnosti konstrukcije NFA stroja za vsak vhod in izhod.