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

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

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

Дефиниција

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

$M=(\Sigma\,, \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$

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

Овај незавршени чланак Детерминистички потисни аутомат везан је за рачунарство. Користећи правила Википедије, можете га проширити.