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:
# Mogu koristiti vrh stoga kako bi odlučili koji prijelaz obaviti
# 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^kb^k | k \ge 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) = \empty  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
* 
* 

## Vanjske veze
* non-deterministic pushdown automaton,  na Planet Math.
* JFLAP, simulator za nekoliko tipova automata, uključujući nedeterministički potisni automat