Teorija automata

Izvor: Wikipedija

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.

Sadržaj

1 Osnovni opis
2 Formalni opis
- 2.1 Definicije
3 Klase automata
- 3.1 Proširenja konačnih automata

[uredi] 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 jezik koji automat prihvaća.

[uredi] Formalni opis

[uredi] 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.

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 $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 $Σ$ , koje dane kao ulaz automata M će ga natjerati da se zaustavi u nekom od stanja iz skupa F.

[uredi] 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 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.
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.

[uredi] 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 $δ$ 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.