Potisni automat

Sa Wikipedije, slobodne enciklopedije
Idi na: navigacija, traži
Question book-new.svg Ovaj članak ili neka od njegovih sekcija nije dovoljno potkrijepljena izvorima (literatura, web stranice ili drugi izvori).
Sporne rečenice i navodi bi mogli, ukoliko se pravilno ne označe validnim izvorima, biti obrisani i uklonjeni. Pomozite Wikipediji tako što ćete navesti validne izvore putem referenci, te nakon toga možete ukloniti ovaj šablon.

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 | uredi izvor]

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 | uredi izvor]

NPA W može biti definisan 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 steka (stekovna 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 steka
  • F je podskup skupa Q 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 \Omega kao početni znak steka, i umjesto istaknutog znaka stekovne abecede dodaju prvi prijelaz koji dodaje početni znak na vrh steka.

Primjer[uredi | uredi izvor]

Kontekstno nezavisni 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 definisanim 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 bilo koji (q, \theta, \rho)


Značenje ovih prijelaza se može objasniti pregledanjem 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 steka te automat prelazi u stanje q_1 i znak \underline{A} je zapisan na vrh steka.

Automateapile.png

Također pogledajte[uredi | uredi izvor]

Vanjski linkovi[uredi | uredi izvor]

Reference[uredi | uredi izvor]

  • 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.