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

Deterministički potisni automat je slabija verzija potisnog automata.

Definicija[uredi | uredi izvor]

DPA M se može definisati 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 steka (stekovna abeceda)
  • q_0 je početno (ili inicijalno) stanje, element skupa Q
  • Z_0 je početni znak steka, element skupa \Gamma
  • A je skup finalnih stanja, podskup skupa 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 uslova:

  • 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 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 detektiranjem jedinstvenog znaka kojeg na vrh steka dodaje početno stanje.