Deterministički konačni automat

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

DKA 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 = x₀x₁ ... x_n niz znakova nad abecedom Σ. M prihvaća niz znakova X ako niz stanja r₀,r₁, ..., r_n, postoji u S uz sljedeće uslove:

1. r₀ = s
2. r_i+1 = T(r_i, x_i), for i = 0, ..., n-1
3. r_n ∈ 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

Slijedi primjer DKA M nad binarnom abecedom koji određuje sadrži li ulazni niz paran broj znamenki 0.

dijagram stanja za M

M = (S, Σ, T, s, A) gdje je

• S = {S₁, S₂},
• Σ = {0, 1},
• s = S₁,
• A = {S₁}, and
• T je definiran sljedećom tablicom prijelaza:

	0	1
S1	S2	S1
S2	S1	S2

Kratko rečeno, stanje S₁ predstavlja događaj da se u ulaznom nizu dosad pojavio paran broj cifri 0, dok stanje S₂ 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:

${\displaystyle (1^{*}01^{*}01^{*})^{*}\,\!}$

Prednosti i nedostaci

DKAi 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 aⁿbⁿ — 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.

Također pogledajte

• Turingova mašina