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

Из Википедије, слободне енциклопедије

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

Израз потисни се односи на операцију уношења података у стек, (енгл. 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

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