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

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

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

ДефиницијаУреди

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

  где важи:

  •   је коначан скуп улазних знакова(улазна азбука)
  •   је азбука стања
  •   је азбука потисног списка
  •   је почетно стање
  •   је почетни симбол потисног списка
  •  , скуп завршних конфигурација
  •   је скуп правила прелаза.

Петорка   се назива правило, а ако је   онда  -правило.

Конфигурација потисног аутомата М је тројка   где је   реч коју ће аутомат прочитати, а   унутрашња конфигурација аутомата (први карактер ниске   је на врху потисног списка).

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

  • За свако  , скуп   садржи бар један елемент.
  • За свако  , ако је  , тада је   за свако  

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