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

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

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

Дефиниција

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

$M=(Q\,,\Sigma \,,\Gamma \,,q_{0}\,,Z_{0}\,,A\,,\delta \,)$ где важи:

• $Q\,$ је коначан скуп стања
• $\Sigma \,$ је коначан скуп улазних знакова(улазна азбука)
• $\Gamma \,$ је коначан скуп стековних симбола
• $q_{0}\,\in Q\,$ је почетно стаље
• $Z_{0}\,\in \Gamma \,$ је почетни симбол стека
• $A\,\subseteq Q\,$, где је $A$ скуп прихватних, завршних стања
• $\delta \,$ је функција прелаза где је

$\delta \,:(Q\,\times (\Sigma \,\cup \left\{\lambda \,\right\})\times \Gamma \,)\longrightarrow Q\times \Gamma ^{*}$

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

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

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