Teorija automata

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

Osnovni opis

Automat je matematički model za konačni automat (KA). KA je mašina koja, za dati niz znakova (simbola) na ulazu, skače kroz sled stanja zavisno od svoje funkcije prelaza (koja može biti izražena kao tablica prelaza). Ova funkcija prelaza obično govori automatu u koje stanje da napreduje, zavisno od trenutnog stanja i trenutno pročitanog znaka.

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

Zavisno od stanja u kojem se automat nalazi u trenutku stajanja, kažemo da automat ili prihvata ili ne prihvata (odbija) ulaznu reč. Ukoliko je stao u prihvatljivom stanju, tada automat prihvata reč. Inače se nalazi u neprihvatljivom stanju i reč je odbijena. Skup svih reči koje automat prihvata zovemo jezik koji automat prihvata.

Formalni opis

Definicije

Za početak definišemo neke osnovne koncepte univerzalne za sve klase automata:

Znak (simbol)

Arbitrarna oznaka koja ima neko značenje ili utiče na rad mašine.

Reč

Konačni niz znakova (string) oblikovan nadovezivanjem (konkatenacijom) nekog broja znakova.

Abeceda

Konačan skup znakova.

Jezik

Skup reči, oblikovan znakovima u datoj 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 prihvata.
• δ je funkcija prelaza:

$\delta :Q\times \Sigma \rightarrow Q.$

Ova funkcija može biti proširena na način da, umesto 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 sledeći način:

${\hat {\delta }}:Q\times \Sigma ^{\star }\rightarrow Q.$

...gde je ∑^* Kleeneov operator primenjen 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čigledno 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 prihvata 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 reči w nad abecedom $\Sigma$, koje date kao ulaz automata M će ga naterati 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 definisan prelaz za svaki znak ulazne abecede.

Nedeterministički konačni automat (NKA)

Stanja ovog automata ne moraju imati definisan prelaz za svaki znak ulazne abecede, ili mogu imati definisan prelaz u skup stanja. Drugim rečima, funkcija prelaza definiše prelaz u skup stanja koji može biti prazan. Automat prihvata reč ukoliko postoji barem jedan sled prelaza iz početnog stanja S₀ u neko od stanja u skupu F labelirano sa ulaznom reči. Ako je prelaz nedefinisan, na način da automat ne zna kako da nastavi da čita ulazni niz znakova, reč se odbija.

Nedeterministički konačni automat sa ε-prelazima (ε-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 nijedan ulazni znak. Tj. ako stanje ima prelaz označen sa $\epsilon$, tada NKA može biti u bilo kojem od stanja dostižnih sa $\epsilon$-prijelazima, bilo neposredno bilo posredno preko drugih stanja sa definisanim $\epsilon$-prelazima. Skup svih stanja dostižnih 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 predstavljaju istovetne modele izračunljivosti, jednake ekspresivne moći. Za svaki NKA M može biti konstruisan DKA M' koji prihvata isti jezik.

Proširenja konačnih automata

Familija jezika koje prihvataju gore opisani automati se zove familija regularnih jezika. Moćniji automati mogu prihvatiti složenije klase jezika. Takvi automati su:

Potisni automati (PA)

Takva mašina je identična sa DKA (odnosno NKA), osim što je opremljena i sa memorijom u obliku (potisnog) stoga. Funkcija prelaza $\delta$ takođe zavisi od znaka na vrhu stoga, te određuje način na koji će sadržaj stoga biti izmenjen za svaki prelaz. PAi prihvataju klasu kontekstno nezavisnih jezika.

Linearno ograničen automat (LOA)

LOA je ograničena verzija Turingove mašine; umesto beskonačne trake, traka ima dostupno prostora proporcionalno dužini ulazne reči. LOAi prihvatju kontekstno zavisne jezike.

Tjuringove mašine

Ovo su najmoćnije računarske mašine. Poseduju beskonačnu memoriju u obliku trake, i glavu koja može čitati i pisati po traci, i pomicati se u oba smera duž trake. Turingove mašine su kao model izračunljivosti ekvivalentni algoritmima, i predstavljaju teoretsku osnovu modernih računara. Turingove mašine odlučuju rekurzivne jezike i prepoznaju rekurzivno prebrojive jezike.