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.
  • q0 je početno (inicijalno) stanje, tj. stanje u kojem se automat nalazi u trenutku kad još nijedan znak nije obrađen (Očigledno 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 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 S0 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.
Теорија аутомата: формални језици и формалне граматике
Хијерархија
Чомског
Граматике Језици Минимални
аутомат
Тип-0 Без ограничења Рекурзивно пребројиви Тјурингова машина
 % (без уобичајеног имена) Рекурзивни Одлучивач
Тип-1 Контекст сензитивна Контекст сензитивни Линеарно-ограничени
 % Индексирана Индексиран Угњеждени стек
Тип-2 Контекст-слободна Контекст-слободни Недетерминистички потисни
 % Детерминистичка контекст-слободна Детерминистички контекст-слободни Детерминистички потисни
Тип-3 Регуларна Регуларан Коначни
Свака категорија језика или граматика је прави подскуп категорије директно изнад ње.