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.