Potisni automat

Izvor: Wikipedia

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[uredi - уреди]

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[uredi - уреди]

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[uredi - уреди]

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.

Automateapile.png

Također vidjeti[uredi - уреди]

Vanjske poveznice[uredi - уреди]

Izvori[uredi - уреди]

  • Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. 
  • Siniša Srbljić (2003). Jezični procesori 1. Element. ISBN 953-197-129-3. 
Teorija automata: formalni jezici i formalne gramatike
Chomskyjeva
hijerarhija
Gramatike Jezici Minimalni
automat
Tip 0 Neograničenih produkcija Rekurzivno prebrojiv Turingov stroj
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.