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

uredi

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

uredi

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

uredi

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.

 

Također pogledajte

uredi

Vanjski linkovi

uredi

Reference

uredi
  • 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.
Teorija automata: formalni jezici i formalne gramatike
Chomskyjeva
hijerarhija
Gramatike Jezici Minimalni
automat
Tip 0 Neograničenih produkcija Rekurzivno prebrojiv Turingova mašina
n/a (nema uobičajenog imena) Rekurzivni Odlučitelj
Tip 1 Kontekstno ovisna Kontekstno ovisni Linearno ograničen
n/a Indeksirana Indeksirani Ugniježđenog stoga
Tip 2 Kontekstno neovisna Kontekstno neovisni Nedeterministički potisni
n/a Deterministička kontekstno neovisna Deterministički kontekstno neovisni Deterministički potisni
Tip 3 Regularna Regularni Konačni
Svaka kategorija jezika ili gramatika je pravi podskup nadređene kategorije.