Potisni automat

U teoriji automata, potisni automat je konačni automat koji koristi podatkovnu strukturu stek. Termin "potisni" se odnosi na akciju "potiskivanja" (engl. pushing down) kojom bi prototipni mehanički automat fizički doticao bušenu karticu u svrhu iščitavanja njenog sadržaja. Termin "potisni automat" (PA) u teoretskom računarstvu se odnosi na apstraktni matematički automat koji prepoznaje kontekstno nezavisne jezike.

Djelovanje

Potisni se automati razlikuju od normalnog konačnog automata na sljedeća dva načina:

1. Mogu koristiti vrh steka kako bi odlučili koji prijelaz obaviti
2. Mogu manipulisati sadržajem steka prilikom obavljanja prijelaza

Potisni automati odabiru prijelaz indeksiranjem tablice prijelaza sa ulaznim znakom (simbolom), trenutnim stanjem te vrhom steka. Normalni konačni automati koriste samo ulazni znak i trenutno stanje: nemaju steka nad kojim mogu obavljati promjene. Potisni automati dodaju stek kao parametar izbora. Za dati ulazni znak, trenutno stanje te dati znak na vrhu steka, odabire se odgovarajući prijelaz.

Potisni automati također mogu manipulisati stekom prilikom obavljanja prijelaza. Normalni konačni automati kao rezultat obavljanja prijelaza odabiru novo stanje. Prilikom manipulisanja stekom može se na vrh steka dodati (engl. push) određeni znak, ili uzeti (engl. pop) znak sa vrha steka. Automat može alternativno potpuno ignorisati sadržaj steka, ne obavljajući nikakve operacije nad njim. Izbor manipulisanja (ili nemanipulisanja) sadržajem steka je određeno funkcijom prijelaza.

Ukratko: Za dati ulazni znak, trenutno stanje, te znak na vrhu steka, potisni automat može preći u drugo stanje, te opcionalno manipulisati (dodati znak ili uzeti znakove) sadržajem steka.

Ako je (pozadinski) konačni automat konkretno nedeterministički konačni automat, dobijamo automat koji je tehnički poznat pod nazivom "nedeterministički potisni automat" (NPA). Ukoliko se koristi deterministički konačni automat, kao rezultat dobijamo deterministički potisni automat (DPA), strogo slabiji uređaj.

Nedeterminizam u ovom kontekstu ne označava pojavu slučajnih događaja, već označava mogućnost više od jednog prijelaza za dati ulazni znak, stanje i znak na vrhu steka.

Ako dozvolimo konačnom automatu pristup dva steka umjesto samo jednom, dobijemo znatno jači uređaj, istovjetan po moći sa Turingovom mašinom. Linearno ograničen automat je uređaj koji je moćniji od potisnog automata, ali i slabiji od Turingove mašine.

Za svaku kontekstno nezavisnu gramatiku postoji istovjetan potisni automat u smislu da jezik koji gramatika generiše je istovjetan jeziku kojeg automat prihvata. Tako, za svaki potisni automat postoji istovjetna kontekstno nezavisna gramatika takva da jezik koji ona generiše je istovjetan jeziku koji automat prihvata.

Definicija

NPA W može biti definisan kao uređena sedmorka:

$W=(Q,\Sigma ,\Phi ,\sigma ,s,\Omega ,F)$ gdje

• $Q$ je konačan skup stanja
• $\Sigma$ je konačan skup ulaznih znakova (ulazna abeceda)
• $\Phi$ je konačan skup znakova steka (stekovna abeceda)
• $\sigma$ (ili ponekad $\delta$) je konačna relacija prijelaza $(Q\times (\Sigma \cup \left\{\epsilon \right\})\times \Phi )\longrightarrow P(Q\times \Phi ^{*})$
• $s$ je element skupa $Q$ početno (ili inicijalno) stanje
• $\Omega$ je početni znak steka
• $F$ je podskup skupa $Q$ koji čini skup prihvatljivih stanja

Dva su moguća kriterija prihvatanja niza znakova: prihvatanje praznim stekom i prihvatanje prihvatljivim stanjem. Lahko se može pokazati da su oba kriterija istovjetna: konačno stanje može u petlji uzimati znakove sa vrha steka sve dok se sadržaj steka ne isprazni, a i automat može detektovati prazan stek i preći u prihvatljivo stanje detektovanjem jedinstvenog znaka kojeg na vrh steka dodaje početno stanje.

Ponegdje se u formalnoj definiciji potisnog automata koristi i uređena šestorka, izuzimajući $\Omega$ kao početni znak steka, i umjesto istaknutog znaka stekovne abecede dodaju prvi prijelaz koji dodaje početni znak na vrh steka.

Primjer

Kontekstno nezavisni jezik $\{a^{k}b^{k}|k\geq 0\}$ može biti prepoznat sljedećim potisnim automatom:

$M=(\{q_{0},q_{1},q_{2},q_{3}\},\{a,b\},\{A,{\underline {A}}\},\delta ,q_{0},\{q_{0},q_{3}\}),$

sa definisanim prijelazima:

$\delta (q_{0},a,\epsilon )=\{(q_{1},{\underline {A}})\}$

$\delta (q_{1},a,\epsilon )=\{(q_{1},A)\}$

$\delta (q_{1},b,A)=\{(q_{2},\epsilon )\}$

$\delta (q_{1},b,{\underline {A}})=\{(q_{3},\epsilon )\}$

$\delta (q_{2},b,A)=\{(q_{2},\epsilon )\}$

$\delta (q_{2},b,{\underline {A}})=\{(q_{3},\epsilon )\}$

$\delta (q,\theta ,\rho )=\emptyset$ za bilo koji $(q,\theta ,\rho )$

Značenje ovih prijelaza se može objasniti pregledanjem prvog prijelaza

$\delta (q_{0},a,\epsilon )=\{(q_{1},{\underline {A}})\}$

Kada je $q_{0}$ trenutno stanje, $a$ je ulazni znak i $\epsilon$ je uzet sa vrha steka te automat prelazi u stanje $q_{1}$ i znak ${\underline {A}}$ je zapisan na vrh steka.

Također pogledajte

• konačni automat

Vanjski linkovi

• non-deterministic pushdown automaton, Arhivirano 31. 10. 2007. na Wayback Machine na Planet Math.
• JFLAP, simulator za nekoliko tipova automata, uključujući nedeterministički potisni automat

Reference

• Michael Sipser - Introduction to the Theory of Computation, PWS Publishing, 1997; ISBN 0-534-94728-X Sekcija 2.2: Pushdown Automata, pp. 101–114.
• Siniša Srbljić - Jezični Procesori 1, Element, 2003; ISBN 953-197-129-3 Sekcija 3.2: Potisni automat (PA), pp. 103–118.