Potisni automat

U teoriji automata, potisni automat je konačni automat koji koristi podatkovnu strukturu stog. 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 stroj koji prepoznaje kontekstno neovisne jezike.

Djelovanje

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

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

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

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

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

Ako je (pozadinski) konačni automat konkretno nedeterministički konačni automat, dobivamo stroj koji je tehnički poznat pod nazivom "nedeterministički potisni automat" (NPA). Ukoliko se koristi deterministički konačni automat, kao rezultat dobivamo 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 dani ulazni znak, stanje i znak na vrhu stoga.

Ako dozvolimo konačnom automatu pristup dva stoga umjesto samo jednom, dobijemo znatno jači uređaj, istovjetan po moći sa Turingovim strojem. Linearno ograničen automat je uređaj koji je moćniji od potisnog automata, ali i slabiji od Turingovog stroja.

Za svaku kontekstno neovisnu gramatiku postoji istovjetan potisni automat u smislu da jezik koji gramatika generira je istovjetan jeziku kojeg automat prihvaća. Sljedbeno tome, za svaki potisni automat postoji istovjetna kontekstno neovisna gramatika takva da jezik koji ona generira je istovjetan jeziku koji automat prihvaća.

Definicija

NPA W može biti definiran 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 stoga (stogovna 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 stoga
• $F$ je podskup skupa $Q$ koji čini skup prihvatljivih stanja

Dva su moguća kriterija prihvaćanja niza znakova: prihvaćanje praznim stogom i prihvaćanje prihvatljivim stanjem. Lako se može pokazati da su oba kriterija istovjetna: konačno stanje može u petlji uzimati znakove sa vrha stoga sve dok se sadržaj stoga ne isprazni, a i stroj može detektirati prazni stog i preći u prihvatljivo stanje detektiranjem jedinstvenog znaka kojeg na vrh stoga dodaje početno stanje.

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

Primjer

Kontekstno neovisni 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 definiranim 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 svaki drugi $(q,\theta ,\rho )$

Značenje ovih prijelaza se može objasniti pregledavanjem prvog 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 stoga te stroj prelazi u stanje $q_{1}$ i znak ${\underline {A}}$ je zapisan na vrh stoga.

Povezano

• Konačni automat

Literatura

• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. 
• Siniša Srbljić (2003). Jezični procesori 1. Element. ISBN 953-197-129-3. 

Vanjske poveznice

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