Deterministički konačni automat
Ovaj članak ili neki od njegovih odlomaka nije dovoljno potkrijepljen izvorima (literatura, veb-sajtovi ili drugi izvori). |
U teoriji računanja, deterministički konačni automat (DKA) je konačni automat u kojem za svaki par stanja i ulaznog znaka postoji jedan i samo jedan prijelaz u sljedeće stanje. DKAi prepoznaju skup regularnih jezika.
DKA prima niz ulaznih znakova, i za svaki ulazni znak obavlja prijelaz u stanje koje određuje funkcija prijelaza. Kada je pročitan cijeli ulazni niz, prihvatit će ili odbiti niz znakova zavisno od toga da li je DKA u prihvatljivom ili neprihvatljivom stanju.
Formalna definicija
urediDKA se formalno definira uređenom petorkom, (S, Σ, T, s, A), koja se sastoji od
- konačnog skupa stanja (S)
- konačnog skupa ulaznih znakova zvanog ulazna abeceda (Σ)
- funkcije prijelaza (T : S × Σ → S)
- početnog (inicijalnog) stanja (s ∈ S)
- skupa prihvatljivih stanja (A ⊆ S)
Neka je M DKA takav da M = (S, Σ, T, s, A), i X = x0x1 ... xn niz znakova nad abecedom Σ. M prihvaća niz znakova X ako niz stanja r0,r1, ..., rn, postoji u S uz sljedeće uslove:
- r0 = s
- ri+1 = T(ri, xi), for i = 0, ..., n-1
- rn ∈ A.
Kao što je pokazano u prvom uslovu, stroj započinje rad u početnom stanju s. Drugi uslov kaže da će za svaki znak ulaznog niza X stroj preći iz trenutnog stanja u stanje upravljano funkcijom prijelaza T.
Posljednji uslov kaže da stroj prihvata ulazni niz ako posljednji znak ulaznog niza X uzrokuje prijelaz u jedno od prihvatljivih stanja. Inače kažemo da stroj ne prihvata (odbija) ulazni niz. Skup nizova znakova koje DKA prihvaća je oblik formalnog jezika, i predstavlja oblik jezika kojeg DKA prepoznaje.
Primjer
urediSlijedi primjer DKA M nad binarnom abecedom koji određuje sadrži li ulazni niz paran broj znamenki 0.
M = (S, Σ, T, s, A) gdje je
- S = {S1, S2},
- Σ = {0, 1},
- s = S1,
- A = {S1}, and
- T je definiran sljedećom tablicom prijelaza:
0 1 S1 S2 S1 S2 S1 S2
Kratko rečeno, stanje S1 predstavlja događaj da se u ulaznom nizu dosad pojavio paran broj cifri 0, dok stanje S2 predstavlja događaj da se pojavio neparan broj. Cifra 1 u ulaznom nizu ne mijenja stanje automata. Kada se završi čitanje ulaznog niza, trenutno stanje će pokazati da li je ulazni niz sadržavao paran broj cifri 0 ili ne.
Jezik DKA M je regularni jezik opisan sljedećim regularnim izrazom:
Prednosti i nedostaci
urediDKAi su jedni od najpraktičnijih modela računanja, s obzirom da postoji trivijalan online algoritam koji ih simulira u linearnom vremenu i konstantnom prostoru nad tokom ulaznih simbola. Za dva data DKAa postoje djelotvorni algoritmi za pronalaženje DKA koji prepoznaje uniju, presjek te komplement jezika koje oni prepoznaju. Također postoje djelotvorni algoritmi za određivanje da li DKA prihvata bilo koji niz znakova, da li DKA prihvata sve nizove znakova, da li dva DKA prihvataju isti jezik, te za pronalaženje DKA sa minimalnim brojem stanja za zadani jezik.
DKAi su modeli računanja jednake moći kao NKAi (nedeterministički konačni automati).
U drugu ruku, DKAi su strogo ograničene moći nad jezicima koje mogu prepoznati — mnogi jednostavni jezici, uključujući bilo koji problem čije rješenje zahtijeva više nego konstantan prostor, ne mogu biti prepoznati od strane DKA. Kanonski primjer jezika kojeg nijedan DKA ne može prepoznati jest jezik koji se sastoji od nizova znakova oblika anbn — konačan broj znakova a nakon kojeg slijedi jednaki broj znakova b. Može se pokazati da nijedan DKA ne može imati dovoljan broj stanja da prepozna takav jezik.