Deterministički potisni automat

Izvor: Wikipedija
Skoči na: orijentacija, traži

U teoriji automata, deterministički potisni automat je deterministički 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 "deterministički potisni automat" (DPA) u teoretskom računarstvu se odnosi na apstraktni matematički stroj koji prepoznaje determinističke kontekstno neovisne jezike.

Deterministički potisni automat je slabija verzija potisnog automata.

Definicija[uredi VE | uredi]

DPA M se može definirati kao uređena sedmorka:

M=(Q,\Sigma,\Gamma,q_0,Z_0,A,\delta) gdje

  • Q je konačan skup stanja
  • \Sigma je konačan skup ulaznih znakova (ulazna abeceda)
  • \Gamma je konačan skup znakova stoga (stogovna abeceda)
  • q_0 je početno (ili inicijalno) stanje, element skupa Q
  • Z_0 je početni znak stoga, element skupa \Gamma
  • A is the set of final states, a subset of Q
  • \delta je konačna relacija prijelaza(Q \times ( \Sigma \cup \left \{ \Lambda \right \} ) \times \Gamma) \longrightarrow partitivni skup (skup svih podskupova) skupa (Q \times \Gamma ^{*})

M je deterministički ako zadovoljava oba sljedeća uvjeta:

  • Za svaki q \in Q, a \in \Sigma \cup \left \{ \Lambda \right \}, X \in \Gamma, skup \delta(q,a,X) sadrži najviše jedan element.
  • Za svaki q \in Q, X \in \Gamma, ako \delta(q, \Lambda, X) \not= Ø, tada \delta(q,a,X) = Ø za svaki a \in \Sigma

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.

Izvori[uredi VE | uredi]

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.