Deterministički potisni automat

U teoriji automata, deterministički potisni automat je konačni deterministički automat koji u svom radu koristi stek.

Izraz potisni se odnosi na operaciju unošenja podataka u stek, (engl. push, potisnuti), koja dodaje podatak na vrh steka. Termin „deterministički potisni automat“ se u teoriji računarstva odnosi na apstraktni matematički automat koji prepoznaje determinističke kontekstno-nezavisne jezike. Deterministički potisni automat je određena verzija potisnog automata. Interesantno je da deterministički potisni automati spadaju u pravu podgrupu potisnih automata za razliku od deterministički konačnih automata i nedeterministički konačnih automata.

Definicija

Potisni automat 'M' se može definisati kao uređena sedmorka:

$M=(\Sigma \,,\mathbb {Q} ,\Gamma \,,i\,,Z_{0}\,,K\,,\Delta \,)$ gde važi:

• $\Sigma \,$ je konačan skup ulaznih znakova(ulazna azbuka)
• $Q\,$ je azbuka stanja
• $\Gamma \,$ je azbuka potisnog spiska
• $i\,\in Q\,$ je početno stanje
• $Z_{0}\,\in \Gamma \,$ je početni simbol potisnog spiska
• $K\,\subseteq Q\times \Gamma ^{*}$, skup završnih konfiguracija
• $\Delta \,\subseteq Q\,\times (\Sigma \,\cup \left\{\epsilon \,\right\})\times \Gamma \,\times Q\times \Gamma ^{*}$ je skup pravila prelaza.

Petorka $(q,a,Z,r,\gamma )\in \Delta$ se naziva pravilo, a ako je $a=\epsilon \$ onda $\epsilon$-pravilo.

Konfiguracija potisnog automata M je trojka $(q,\omega ,\gamma )\in Q\times \Sigma ^{*}\times \Gamma ^{*}$ gde je $\omega \$ reč koju će automat pročitati, a $(q,\gamma )$ unutrašnja konfiguracija automata (prvi karakter niske $\gamma \$ je na vrhu potisnog spiska).

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

• Za svako $q\in Q,a\in \Sigma \cup \left\{\epsilon \right\},x\in \Gamma$, skup $\Delta (q,a,x)\,$ sadrži bar jedan element.
• Za svako $q\in Q,x\in \Gamma$, ako je $\Delta (q,\epsilon ,x)\not =\emptyset \,$, tada je $\Delta \left(q,a,x\right)=\emptyset$ za svako $a\in \Sigma$

Postoje dva moguća kriterijuma za prihvatanje znakova: prihvatanje praznim potisnim spiskom i prihvatanje završnim stanjem. Ova dva kriterijuma nisu jednaka za determinističke potisne automate iako jesu za nedeterminističke potisne automate.