Deterministički potisni automat

Ovaj članak ili neki od njegovih odlomaka nije dovoljno potkrijepljen izvorima (literatura, veb-sajtovi ili drugi izvori). Ako se pravilno ne potkrijepe pouzdanim izvorima, sporne rečenice i navodi mogli bi biti izbrisani. 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.

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

${\displaystyle M=(Q,\Sigma ,\Gamma ,q_{0},Z_{0},A,\delta )}$ gdje

• ${\displaystyle Q}$ je konačan skup stanja
• ${\displaystyle \Sigma }$ je konačan skup ulaznih znakova (ulazna abeceda)
• ${\displaystyle \Gamma }$ je konačan skup znakova steka (stekovna abeceda)
• ${\displaystyle q_{0}}$ je početno (ili inicijalno) stanje, element skupa ${\displaystyle Q}$
• ${\displaystyle Z_{0}}$ je početni znak steka, element skupa ${\displaystyle \Gamma }$
• ${\displaystyle A}$ je skup finalnih stanja, podskup skupa ${\displaystyle Q}$
• ${\displaystyle \delta }$ je konačna relacija prijelaza${\displaystyle (Q\times (\Sigma \cup \left\{\Lambda \right\})\times \Gamma )\longrightarrow }$ partitivni skup (skup svih podskupova) skupa ${\displaystyle (Q\times \Gamma ^{*})}$

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

• Za svaki ${\displaystyle q\in Q,a\in \Sigma \cup \left\{\Lambda \right\},X\in \Gamma }$, skup ${\displaystyle \delta (q,a,X)}$ sadrži najviše jedan element.
• Za svaki ${\displaystyle q\in Q,X\in \Gamma }$, ako ${\displaystyle \delta (q,\Lambda ,X)\not =}$Ø, tada ${\displaystyle \delta (q,a,X)=}$Ø za svaki ${\displaystyle 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.