Deterministički konačni automat

U teoriji izračunljivosti, 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. Deterministički konačni automati 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 ovisno o tome je li DKA u prihvatljivom ili neprihvatljivom stanju.

Formalna definicija

DKA se formalno definira uređenom petorkom, $\left(Q,\Sigma ,\delta ,q_{0},F\right)$, koja se sastoji od

• konačnog skupa stanja ($Q$)
• konačnog skupa ulaznih znakova zvanog ulazna abeceda ($\Sigma$)
• funkcije prijelaza ($\delta :Q\times \Sigma \rightarrow Q$)
• početnog (inicijalnog) stanja ($q_{0}\in Q$)
• skupa prihvatljivih stanja ($F\subseteq Q$)

Neka je M DKA takav da M = $\left(Q,\Sigma ,\delta ,q_{0},F\right)$, i $X=x_{0}x_{1}...x_{n}$ niz znakova nad abecedom $\Sigma$. M prihvaća niz znakova $X$ ako slijed stanja $r_{0},r_{1},...,r_{n}$, postoji u $Q$ uz sljedeće uvjete:

1. $r_{0}=q_{0}$
2. $r_{i+1}=\delta (r_{i},x_{i})$ za $i=0,...,n-1$
3. $r_{n}\in F$

Kao što je pokazano u prvom uvjetu, stroj započinje rad u početnom stanju s. Drugi uvjet kaže da će za svaki znak ulaznog niza X stroj preći iz trenutačnoga stanja u stanje upravljano funkcijom prijelaza $\delta$. Posljednji uvjet kaže da stroj prihvaća ulazni niz ako posljednji znak ulaznog niza X uzrokuje prijelaz u jedno od prihvatljivih stanja. Inače kažemo da stroj ne prihvaća (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 = $\left(Q,\Sigma ,\delta ,q_{0},F\right)$ gdje je

• $Q=\left\{{S_{1},S_{2}}\right\}$
• $\Sigma =\left\{{0,1}\right\}$
• $q_{0}=S_{1}$
• $F=\left\{{S_{1}}\right\}$, te
• $\delta$ je definirana 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 znamenki 0, dok stanje S₂ predstavlja događaj da se pojavio neparan broj. Znamenka 1 u ulaznom nizu ne mijenja stanje automata. Kada se završi čitanje ulaznog niza, trenutačno će stanje pokazati da li je ulazni niz sadržavao paran broj znamenki 0 ili ne.

Jezik DKA M je regularni jezik opisan sljedećim regularnim izrazom:

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

Prednosti i nedostatci

DKAi jedni su od najpraktičnijih modela izračunljivosti, s obzirom da postoji trivijalan online algoritam koji ih simulira u linearnom vremenu i konstantnom prostoru nad tijekom ulaznih simbola. Za dva dana DKAa postoje učinkoviti algoritmi za pronalaženje DKA koji prepoznaje uniju, presjek te komplement jezika koje oni prepoznaju. Također postoje učinkoviti algoritmi za određivanje da li DKA prihvaća bilo koji niz znakova, da li DKA prihvaća sve nizove znakova, da li dva DKA prihvaćaju isti jezik, te za pronalaženje DKA sa minimalnim brojem stanja za zadani jezik.

DKAi su modeli izračunljivosti 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 kojega 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.

Vidjeti također

• Aciklički deterministički konačni automat