Teorija automata

U teoretskom računarstvu, **teorija automata** je disciplina koja se bavi proučavanjem apstraktnih strojeva i problema koje oni mogu riješiti. Teorija automata je usko povezana sa teorijom formalnih jezika, s obzirom da su sami automati često klasificirani klasom formalnih jezika koje mogu prepoznati.

## Osnovni opis
Automat je matematički model za konačni automat (KA). KA je stroj koji, za dani niz znakova (simbola) na ulazu, *skače* kroz slijed stanja ovisno o svojoj funkciji prijelaza (koja može biti izražena kao tablica prijelaza). Ova funkcija prijelaza obično govori automatu u koje stanje da napreduje, ovisno o trenutnom stanju i trenutno pročitanom znaku.

Ulaz se *čita* znak po znak, sve dok nije u potpunosti pročitan (ovo si možemo zorno predočiti kao traku sa napisanom riječi koju čita glava za čitanje automata; glava se pomiče nadesno čitajući jedan po jedan znak). Jednom kad je ulazna riječ u cijelosti pročitana, kažemo da automat *staje*.

Ovisno o stanju u kojem se automat nalazi u trenutku stajanja, kažemo da automat ili *prihvaća* ili *ne prihvaća* (*odbija*) ulaznu riječ. Ukoliko je stao u *prihvatljivom stanju*, tada automat *prihvaća* riječ. Inače se nalazi u *neprihvatljivom stanju* i riječ je *odbijena*. Skup svih riječi koje automat prihvaća zovemo *[[formalni jezik|jezik]] koji automat prihvaća*.

## Formalni opis
### Definicije
Za početak definiramo neke osnovne koncepte univerzalne za sve klase automata:
; Znak (simbol) : Arbitrarna oznaka koja ima neko značenje ili utječe na rad stroja.
; Riječ : Konačni niz znakova (string) oblikovan nadovezivanjem (konkatenacijom) nekog broja znakova.
; Abeceda : Konačan skup znakova.
; Jezik : Skup riječi, oblikovan znakovima u danoj abecedi. Može ali ne mora biti beskonačan.
; Automat : formalno, automat je predstavljen uređenom petorkom \langle Q, \Sigma, \delta, q_0, F\rangle gdje je:
* Q je konačan skup *stanja*.
* ∑ je konačan skup *znakova*, kojeg zovemo *abeceda* jezika kojeg automat prihvaća.
* δ je *funkcija prijelaza*:
\delta:Q \times \Sigma \rightarrow Q.
:Domena ove funkcije može biti proširena na način da, umjesto da kao argument prima samo jedan znak abecede, prima niz znakova i vraća stanje u kojem automat ostaje nakon obrađivanja ulaznog niza. Ovo može biti napisano na sljedeći način:
\hat\delta:Q \times \Sigma^{\star} \rightarrow Q.
:...gdje je ∑* Kleeneov operator primjenjen nad skupom ∑.
:Definicija δ je nešto složenija za nedeterminističke i nekonačne automate.
* q0 je početno (inicijalno) stanje, tj. stanje u kojem se automat nalazi u trenutku kad još nijedan znak nije obrađen (Očito je q0∈ Q).
* F je podskup skupa stanja Q (tj. F⊆Q), kojeg zovemo *skup prihvatljivih stanja*
Uzimajući u obzir ove definicije, možemo sad reći da jezik L kojeg prihvaća deterministički konačni automat M=\langle Q, \Sigma, \delta, q_0, F\rangle je:
L= \{ w \in \Sigma^{\star}|\hat\delta(q_0,w)\in F\}
Tj. skup svih riječi w nad abecedom \Sigma, koje dane kao ulaz automata M će ga natjerati da se zaustavi u nekom od stanja iz skupa F.

## Klase automata
Tri su osnovne vrste konačnih automata:
; Deterministički konačni automat (DKA) : Svako stanje ovog automata ima definiran prijelaz za svaki znak ulazne abecede.

; Nedeterministički konačni automat (NKA) : Stanja ovog automata ne moraju imati definiran prijelaz za svaki znak ulazne abecede, ili mogu imati definiran prijelaz u skup stanja. Drugim riječima, funkcija prijelaza definira prijelaz u skup stanja koji može biti prazan. Automat prihvaća riječ ukoliko postoji barem jedan slijed prijelaza iz početnog stanja S0 u neko od stanja u skupu F *labelirano* sa ulaznom riječi. Ako je prijelaz *nedefiniran*, na način da automat ne zna kako nastaviti čitati ulazni niz znakova, riječ se odbija.

; Nedeterministički konačni automat sa ε-prijelazima (ε-NKA) : Osim što mogu skočiti u jedno ili više stanja za bilo koji ulazni znak, ovi automati mogu skočiti ne čitajući niti jedan ulazni znak. Tj. ako stanje ima prijelaz označen sa \epsilon, tada NKA može *biti* u bilo kojem od stanja dohvatljivih sa \epsilon-prijelazima, bilo izravno bilo posredno preko drugih stanja sa definiranim \epsilon-prijelazima. Skup svih stanja dohvatljivih na ovaj način iz stanja q se zove \epsilon-okruženje od q.
Može se formalno pokazati da sve tri vrste automata **mogu prihvatiti isti jezik** i u tom smislu prestavljaju istovjetne modele izračunljivosti, jednake ekspresivne moći. Za svaki NKA M može biti konstruiran DKA M' koji prihvaća isti jezik.

### Proširenja konačnih automata
Familija jezika koje prihvaćaju gore opisani automati se zove familija regularnih jezika. Moćniji automati mogu prihvatiti složenije klase jezika. Takvi automati su:
; Potisni automati (PA) : Takav stroj je identični sa DKA (odnosno NKA), osim što je opremljen i sa memorijom u obliku (potisnog) stoga. Funkcija prijelaza \delta također ovisi o znaku na vrhu stoga, te određuje način na koji će sadržaj stoga biti izmjenjen za svakog prijelaza. PAi prihvaćaju klasu kontekstno neovisnih jezika.
; Linearno ograničen automat (LOA) : LOA je ograničena verzija Turingovog stroja; umjesto beskonačne trake, traka ima dostupno prostora proporcionalno duljini ulazne riječi. LOAi prihvaćaju kontekstno ovisne jezike.
; Turingovi strojevi : Ovo su najmoćniji komputacijski strojevi. Posjeduju beskonačnu memoriju u obliku trake, i glavu koja može čitati i pisati po traci, te se pomicati u oba smjera duž trake. Turingovi strojevi su kao model izračunljivosti ekvivalentni algoritmima, i predstavljaju teoretsku osnovu modernih računala. Turingovi strojevi odlučuju rekurzivne jezike i prepoznaju rekurzivno prebrojive jezike.