Детерминистички потисни аутомат — разлика између измена
м r2.7.1) (Робот: додато pt:Autômato com pilha determinístico |
м Бот: Селим 5 међујезичких веза, које су сад на Википодацима на d:q378713 |
||
Ред 34: | Ред 34: | ||
[[Категорија:Преводиоци (рачунарство)]] |
[[Категорија:Преводиоци (рачунарство)]] |
||
[[bs:Deterministički potisni automat]] |
|||
[[en:Deterministic pushdown automaton]] |
|||
[[hr:Deterministički potisni automat]] |
|||
[[pl:Deterministyczny automat ze stosem]] |
|||
[[pt:Autômato com pilha determinístico]] |
[[pt:Autômato com pilha determinístico]] |
||
[[zh:确定下推自动机]] |
Верзија на датум 11. март 2013. у 09:57
У теорији аутомата, детерминистички потисни аутомат је коначни детерминистички аутомат који у свом раду користи стек.
Израз потисни се односи на операцију уношења података у стек, (енгл. push, потиснути), која додаје податак на врх стека. Термин „детерминистички потисни аутомат“ се у теорији рачунарства односи на апстрактни математички аутомат који препознаје детерминистичке контекстно-независне језике. Детерминистички потисни аутомат је одређена верзија потисног аутомата. Интересантно је да детерминистички потисни аутомати спадају у праву подгрупу потисних аутомата за разлику од детерминистички коначних аутомата и недетерминистички коначних аутомата.
Дефиниција
Потисни аутомат 'M' се може дефинисати као уређена седморка:
где важи:
- је коначан скуп улазних знакова(улазна азбука)
- је азбука стања
- је азбука потисног списка
- је почетно стање
- је почетни симбол потисног списка
- , скуп завршних конфигурација
- је скуп правила прелаза.
Петорка се назива правило, а ако је онда -правило.
Конфигурација потисног аутомата М је тројка где је реч коју ће аутомат прочитати, а унутрашња конфигурација аутомата (први карактер ниске је на врху потисног списка).
M је детерминистички ако задовољава оба следећа услова:
- За свако , скуп садржи бар један елемент.
- За свако , ако је , тада је за свако
Постоје два могућа критеријума за прихватање знакова: прихватање празним потисним списком и прихватање завршним стањем. Ова два критеријума нису једнака за детерминистичке потисне аутомате иако јесу за недетерминистичке потисне аутомате.