Deterministički potisni automat

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

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.