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

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

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

Дефиниција

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

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

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

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

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

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

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

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