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

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

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

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

Дефиниција[уреди]

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

где важи:

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

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

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

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

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

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