Potisni automat: razlika između inačica

Izbrisani sadržaj Dodani sadržaj
PA, formalna definicija + primjer
(Nema razlike inačica)

Inačica od 29. prosinca 2006. u 17:53

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:

  gdje

  •   je konačan skup stanja
  •   je konačan skup ulaznih znakova (ulazna abeceda(racunarstvo))
  •   je konačan skup znakova stoga (stogovna abeceda)
  •   (ili ponekad  ) je konačna relacija prijelaza  
  •   je element skupa   početno (ili inicijalno) stanje
  •   je početni znak stoga
  •   je podskup skupa   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 satnje.

Ponegdje se u formalnoj definiciji potisnog automata koristi i uređena šestorka, izuzimajući   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   može biti prepoznat sljedećim potisnim automatom:

 

sa definiranim prijelazima:

 

 

 

 

 

 

  for any other  


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

 

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

 

Također vidjeti

Vanjske poveznice

Reference

  • Michael Sipser. 1997. Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X Section 2.2: Pushdown Automata, pp.101–114.
  • Siniša Srbljić. 2003. Jezični Procesori 1. Element. ISBN 953-197-129-3 Sekcija 3.2: Potisni automat (PA), pp.103–118.