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č. Ako 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 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 [math]\displaystyle{ \langle Q, \Sigma, \delta, q_0, F\rangle }[/math] gdje je:

• Q je konačan skup stanja.
• ∑ je konačan skup znakova, kojeg zovemo abeceda jezika kojeg automat prihvaća.
• δ je funkcija prijelaza:

[math]\displaystyle{ \delta:Q \times \Sigma \rightarrow Q. }[/math]

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:

[math]\displaystyle{ \hat\delta:Q \times \Sigma^{\star} \rightarrow Q. }[/math]

...gdje je ∑^* Kleeneov operator primijenjen nad skupom ∑.

Definicija δ je nešto složenija za nedeterminističke i nekonačne automate.

• q₀ je početno (inicijalno) stanje, tj. stanje u kojem se automat nalazi u trenutku kad još nijedan znak nije obrađen (Očito je q₀∈ 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 [math]\displaystyle{ L }[/math] kojeg prihvaća deterministički konačni automat [math]\displaystyle{ M=\langle Q, \Sigma, \delta, q_0, F\rangle }[/math] je:

[math]\displaystyle{ L= \{ w \in \Sigma^{\star}|\hat\delta(q_0,w)\in F\} }[/math]

Tj. skup svih riječi w nad abecedom [math]\displaystyle{ \Sigma }[/math], 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.

DKA

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č ako postoji barem jedan slijed prijelaza iz početnog stanja S₀ 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.

NKA, istovjetan DKA iz prethodnog primjera

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 [math]\displaystyle{ \epsilon }[/math], tada NKA može biti u bilo kojem od stanja dohvatljivih sa [math]\displaystyle{ \epsilon }[/math]-prijelazima, bilo izravno bilo posredno preko drugih stanja sa definiranim [math]\displaystyle{ \epsilon }[/math]-prijelazima. Skup svih stanja dohvatljivih na ovaj način iz stanja q se zove [math]\displaystyle{ \epsilon }[/math]-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 [math]\displaystyle{ \delta }[/math] 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.