Potisni automat

S Vikipedije, slobodne enciklopedije

U teoriji automata, potisni automat je konačni automat koji koristi stek za čuvanje podataka.

Rad[uredi | uredi izvor]

dijagram potisnog automata

Potisni automati se od ostalih konačnih automata razlikuju u dva aspekta:

  1. Mogu da koriste vrh steka da odrede koji prelaz da iskoriste.
  2. Mogu da manipulišu stekom tokom sprovođenja prelaza.

Potisni automati biraju prelaz indeksiranjem tabele po ulaznom signalu, trenutnom stanju, i vrhu steka. Obični končani automati gledaju samo ulazni signal i trenutno stanje: oni ne poseduju stek. Potisni automati dodaju stek kao parametar pri izboru. Za dati ulazni signal, trenutno stanje, i simbol na vrhu steka, određuje se prelaz koji će se izvršiti.

Potisni automati takođe mogu da manipulišu stekom u toku sprovođenja prelaza. Obični konačni automati biraju novo stanje koje je rezultat sprovedenog prelaza. Pomenuta manipulacija može da se sastoji u guranju određenog simbola na vrh steka ili u skidanju simbola sa vrha steka. Takođe, automat može da ignoriše stek i da ga ostavi u istom stanju u kome je bio. Izbor manipulacije (ili njenog odsustva) je određen tablicom prelaza.

Ukratko: Za dati ulazni signal, trenutno stanje i simbol na vrhu steka, automat može da prati prelaz u neko naredno stanje i da opcionalno manipuliše (izvrši operaciju umetanja ili skidanja) nad stekom.

Načelno, potisni automat može da sprovede nekoliko računskih operacija nad datom ulaznom niskom, od kojih neke mogu da se završe zaustavljanjem i prihvatanjem niske, dok kod drugih to nije slučaj. Stoga se javlja model koji je poznat pod nazivom nedeterministički potisni automat. Nedeterminizam se sastoji u tom eda može da postoji više dostupnih prelaza za dati ulazni signal, stanje i simbol sa vrha steka. Ako u svakoj situaciji postoji tačno jedan dostupan prelaz, onda se radi o determinističkom potisnom automatu, što je strogo slabiji uređaj.

Ako se konačni automat konstruiše tako da može da radi sa ne jednim već dva steka, onda se dobija moćniji uređaj, koji je po snazi ekvivalentan Tjuringovoj mašini. Linearno ograničen automat je uređaj koji je moćniji od potisnog automata, ali manje moćan od Tjuringove mašine.

Potisni automati su ekvivalenni kontekstno slobodnim gramatikama: za svaku kontekstno-slobodnu gramatiku postoji potisni automat, takav da je jezik generisan gramatikom identičan jeziku koji automat prepoznaje, što je jednostavno dokazati. Teže je pokazati obratni slučaj: da za svaki potisni automat postoji kontekstno slobodna gramatika takva da je jezik koji automat prepoznaje identičan jeziku generisanom tom gramatikom.

Formalna definicija[uredi | uredi izvor]

Potisni automat se formalno definiše kao uređena sedmorka:

gde je

  • konačni skup stanja
  • je konačan skup koji se naziva ulaznom azbukom
  • je koanačan skup koji se naziva azbukom steka
  • je konačan podskup od , relacija prelaza.
  • je početno stanje
  • je početni simbol na steku
  • je skup prihvatajućih stanja

Element je prelaz automata . To znači da , u stanju , sa simbolom na ulazu i sa simbolom na vrhu steka, treba da pročita simbol , promeni stanje u , skine sa vrha steka , i zameni ga simbolom . Slovo (epsilon) označava praznu nisku a '' komponenta relacije prelaza se koristi da formalizuje činjenicu da potisni automat može da bilo pročita slovo sa ulaza ili da nastavi, ostavivši ulaz nedirnut.

Često se u literaturi relacija prelaza zamenjuje (ekvivalentnom) formalizacijom, gde

  • je funkcija prelaza, koja preslikava u konačan podskup od .

Ovde sadrži sve moguće akcije u stanju sa na vrhu steka kada se na ulazu javi . Zapisuje se za funkciju kada važi za relaciju. Treba imati u vidu da je ključna reč u definiciji konačan.

Računanja

Korak potisnog automata

Kako bi se formalizovala semantika potisnog automata, uvodi se opis trenutne situacije. Svaka uređena trojka se naziva trenutnim opisom , koji uključuje trenutno stanje, deo ulazne trake koji još nije pročitan, i sadržaj steka (simbol koji je na vrhu se nalazi na početku). Relacija prelaza definiše korka-relaciju automata za trenutni opis. Za instrukciju postoji korak , za svako i za svako .

Načelno, potisni automati su nedeterministički, što znači da za dati trenutni opis može da postoji više dostupnih koraka. Svaki od ovih koraka može da bude izabran prilikom izračunavanja.

Kod gornje definicije, u svakom koraku se uvek jedan simbol (vrh steka) skida sa steka, i zamenjuje ga onoliko simbola koliko je potrebno. Posledica toga je da nema koraka koji su definisani nad praznim stekom.

Računanja potisnog automata su nizovi koraka. Izračunavanje počinje u početnom stanju sa početnim stek simbolom na steku, i niskom na ulaznoj traci, pa je inicijalni opis . Postoje dva načina prihvatanja. Potisni automat može bilo da prihvati nisku svojim konačnim stanjem, što znači da se nakon što je pročitao ulaznu traku automat nalazi u prihvatajućem stanju (u ), ili da prihvati praznim stekom (), što znači da je čitanje ulaza ispraznilo stek. Prvi način prihvatanja koristi unutrašnju memoriju (stanje), dok drugi koristi spoljašnju memoriju (stek).

Formalno se definiše

  1. za i (konačno stanje)
  2. za (prazan stek)

Ovde predstavlja refleksivno i tranzitivno zatvorenje koraka relacije što znači bilo koji broj uzastopnih koraka (nula, jedan ili više).

Teorema. Za svaki potisni automat može da se konstruiše potisni automat takav da je , i obratno, za svaki potisni automat može da se konstriše potisni automat takav da je


Vidi još[uredi | uredi izvor]

Reference[uredi | uredi izvor]

Spoljašnje veze[uredi | uredi izvor]