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:
 Mogu koristiti vrh steka kako bi odlučili koji prijelaz obaviti
 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:

gdje

 je konačan skup stanja
 je konačan skup ulaznih znakova (ulazna abeceda)
 je konačan skup znakova steka (stekovna abeceda)
 (ili ponekad ) je konačna relacija prijelaza 
 je element skupa  početno (ili inicijalno) stanje
 je početni znak steka
 je podskup skupa  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  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  može biti prepoznat sljedećim potisnim automatom:

sa definisanim prijelazima:

 za bilo koji 

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

Kada je  trenutno stanje,  je ulazni znak i  je uzet sa vrha steka te automat prelazi u stanje  i znak  je zapisan na vrh steka.

Datoteka:Automateapile.png

 Također pogledajte 
 konačni automat

 Vanjski linkovi 
 non-deterministic pushdown automaton,  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;  Sekcija 2.2: Pushdown Automata, pp. 101–114.
 Siniša Srbljić - Jezični Procesori 1, Element, 2003;  Sekcija 3.2: Potisni automat (PA), pp. 103–118.

Kategorija:Teorija automata