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[uredi | uredi kod]
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 jezik koji automat prihvaća.
Formalni opis[uredi | uredi kod]
Definicije[uredi | uredi kod]
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 gdje je:
- Q je konačan skup stanja.
- ∑ je konačan skup znakova, kojeg zovemo abeceda jezika kojeg automat prihvaća.
- δ je funkcija prijelaza:
- 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:
- ...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 kojeg prihvaća deterministički konačni automat je:
Tj. skup svih riječi w nad abecedom , koje dane kao ulaz automata M će ga natjerati da se zaustavi u nekom od stanja iz skupa F.
Klase automata[uredi | uredi kod]
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 , tada NKA može biti u bilo kojem od stanja dohvatljivih sa -prijelazima, bilo izravno bilo posredno preko drugih stanja sa definiranim -prijelazima. Skup svih stanja dohvatljivih na ovaj način iz stanja q se zove -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[uredi | uredi kod]
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 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.
Teorija automata: formalni jezici i formalne gramatike | |||
---|---|---|---|
Chomskyjeva hijerarhija |
Gramatike | Jezici | Minimalni automat |
Tip 0 | Neograničenih produkcija | Rekurzivno prebrojiv | Turingov stroj |
n/a | (nema uobičajenog imena) | Rekurzivni | Odlučitelj |
Tip 1 | Kontekstno ovisna | Kontekstno ovisni | Linearno ograničen |
n/a | Indeksirana | Indeksirani | Ugniježđenog stoga |
Tip 2 | Kontekstno neovisna | Kontekstno neovisni | Nedeterministički potisni |
n/a | Deterministička kontekstno neovisna | Deterministički kontekstno neovisni | Deterministički potisni |
Tip 3 | Regularna | Regularni | Konačni |
Svaka kategorija jezika ili gramatika je pravi podskup nadređene kategorije. |