Детерминистички потисни аутомат — разлика између измена

м
нема описа измене
м (Правопис и/или генералне преправке)
мНема описа измене
У [[теорија аутомата|теорији аутомата]], '''детерминистички [[потисни аутомат]]''' је [[коначни детерминистички аутомат]] који у свом раду користи [[стек (структура података)|стек]].
Израз ''потисни'' се односи на операцију уношења података у стек, ({{Јез-ен|push}}, потиснути), која додаје податак на врх стека. Термин "детерминистички„детерминистички потисни аутомат"аутомат“ се у теорији рачунарства односи на
апстрактни математички аутомат који препознаје детерминистичке контекстно-независне језике.
Детерминистички потисни аутомат је одређена верзија потисног аутомата. Интересантно је да детерминистички потисни аутомати спадају у праву подгрупу потисних аутомата ѕаза разлику од детерминистички коначних аутомата и недетерминистички коначних аутомата.
 
 
== Дефиниција ==
*<math>\Sigma\,</math> је коначан скуп улазних знакова(улазна азбука)
*<math> Q\,</math> је азбука стања
*<math>\Gamma\,</math> је азбука потиснепотисног листесписка
*<math>i\,\in Q\,</math> је почетно стање
*<math>Z_0\,\in\Gamma\,</math> је почетни симбол потиснепотисног листесписка
*<math>K\,\subseteq Q \times \Gamma ^{*}</math>, скуп завршних конфигурација
*<math>\Delta\,\subseteq Q\, \times (\Sigma\, \cup \left \{ \epsilon\, \right \}) \times \Gamma\,\times Q \times \Gamma ^{*}</math> је скуп правила прелаза.
 
Конфигурација потисног аутомата М је тројка <math>(q,\omega,\gamma) \in Q \times \Sigma ^{*} \times \Gamma ^{*}</math>
где је <math> \omega\ </math> реч коју ће аутомат прочитати, а <math>( q, \gamma) </math> унутрашња конфигурација аутомата (први карактер ниске <math> \gamma\ </math> је на врху потиснепотисног листесписка).
 
''M'' је '''''детерминистички''''' ако задовољава оба следећа услова:
* За свако <math> q \in Q, a \in \Sigma \cup \left \{ \epsilon \right \}, x \in \Gamma</math>, скуп <math>\Delta(q,a,x)\,</math> садржи бар један елемент.
* За свако <math> q \in Q, x \in \Gamma</math>, ако је <math>\Delta(q, \epsilon, x) \not= \emptyset\,</math>, тада је <math>\Delta\left( q,a,x \right) = \emptyset</math> за свако <math>a \in \Sigma</math>
Постоје два могућа критеријума за прихватање знакова: прихватање празномпразним потисномпотисним листомсписком и прихватање завршним стањем. Ова два критеријума нису једнака за детерминистичке потисне аутомате иако јесу за недетерминистичке потисне аутомате.
 
{{клица-комп}}