Детерминистички потисни аутомат

У теорији аутомата, детерминистички потисни аутомат је коначни детерминистички аутомат који у свом раду користи стек.

Израз потисни се односи на операцију уношења података у стек, (Шаблон:Јез-ен, потиснути), која додаје податак на врх стека. Термин „детерминистички потисни аутомат“ се у теорији рачунарства односи на апстрактни математички аутомат који препознаје детерминистичке контекстно-независне језике. Детерминистички потисни аутомат је одређена верзија потисног аутомата. Интересантно је да детерминистички потисни аутомати спадају у праву подгрупу потисних аутомата за разлику од детерминистички коначних аутомата и недетерминистички коначних аутомата.

Дефиниција

Потисни аутомат 'M' се може дефинисати као уређена седморка:

$M=(\mathrm{\Sigma },\mathbb{Q},\mathrm{\Gamma },i,Z_0,K,\mathrm{\Delta })$ где важи:

• $\mathrm{\Sigma }$ је коначан скуп улазних знакова(улазна азбука)
• $Q$ је азбука стања
• $\mathrm{\Gamma }$ је азбука потисног списка
• $i\in Q$ је почетно стање
• $Z_0\in \mathrm{\Gamma }$ је почетни симбол потисног списка
• $K\subseteq Q\times {\mathrm{\Gamma }}^{*}$, скуп завршних конфигурација
• $\mathrm{\Delta }\subseteq Q\times (\mathrm{\Sigma }\cup \left\{ϵ\right\})\times \mathrm{\Gamma }\times Q\times {\mathrm{\Gamma }}^{*}$ је скуп правила прелаза.

Петорка $(q,a,Z,r,\gamma )\in \mathrm{\Delta }$ се назива правило, а ако је $a=ϵ$ онда $ϵ$-правило.

Конфигурација потисног аутомата М је тројка $(q,\omega ,\gamma )\in Q\times {\mathrm{\Sigma }}^{*}\times {\mathrm{\Gamma }}^{*}$ где је $\omega$ реч коју ће аутомат прочитати, а $(q,\gamma )$ унутрашња конфигурација аутомата (први карактер ниске $\gamma$ је на врху потисног списка).

M је детерминистички ако задовољава оба следећа услова:

• За свако $q\in Q,a\in \mathrm{\Sigma }\cup \left\{ϵ\right\},x\in \mathrm{\Gamma }$, скуп $\mathrm{\Delta }(q,a,x)$ садржи бар један елемент.
• За свако $q\in Q,x\in \mathrm{\Gamma }$, ако је $\mathrm{\Delta }(q,ϵ,x)=\mathrm{\varnothing }$, тада је $\mathrm{\Delta }(q,a,x)=\mathrm{\varnothing }$ за свако $a\in \mathrm{\Sigma }$

Постоје два могућа критеријума за прихватање знакова: прихватање празним потисним списком и прихватање завршним стањем. Ова два критеријума нису једнака за детерминистичке потисне аутомате иако јесу за недетерминистичке потисне аутомате.