Детерминистички потисни аутомат — разлика између измена
Нема описа измене |
|||
Ред 20: | Ред 20: | ||
:<math>\delta\,:(Q\, \times ( \Sigma\, \cup \left \{ \lambda\, \right \} ) \times \Gamma\,) \longrightarrow Q \times \Gamma ^{*}</math> |
:<math>\delta\,:(Q\, \times ( \Sigma\, \cup \left \{ \lambda\, \right \} ) \times \Gamma\,) \longrightarrow Q \times \Gamma ^{*}</math> |
||
''M'' је детерминистички ако задовољава оба следећа услова: |
''M'' је детерминистички ако задовољава оба следећа услова: |
||
* За свако<math>q \in Q, a \in \Sigma \cup \left \{ \lambda \right \}, x \in \Gamma</math>,скуп <math>\delta(q,a,x)\,</math> садржи бар један елемент. |
* За свако <math> q \in Q, a \in \Sigma \cup \left \{ \lambda \right \}, x \in \Gamma</math>,скуп <math>\delta(q,a,x)\,</math> садржи бар један елемент. |
||
* За свако <math>q \in Q, x \in \Gamma</math>, ако је <math>\delta(q, \lambda, x) \not= \emptyset\,</math>, тада је <math>\delta\left( q,a,x \right) = \emptyset</math> за свако <math>a \in \Sigma</math> |
* За свако <math> q \in Q, x \in \Gamma</math>, ако је <math>\delta(q, \lambda, x) \not= \emptyset\,</math>, тада је <math>\delta\left( q,a,x \right) = \emptyset</math> за свако <math>a \in \Sigma</math> |
||
Постоје два могућа критеријума за прихватање знакова:прихватање праѕном потисном листом и прихватање завршним стањем.Ова два критеријума нису једнака за детерминистичке потисне аутомате иако јесу за недетерминистичке потисне аутомате. |
Постоје два могућа критеријума за прихватање знакова:прихватање праѕном потисном листом и прихватање завршним стањем.Ова два критеријума нису једнака за детерминистичке потисне аутомате иако јесу за недетерминистичке потисне аутомате. |
||
Верзија на датум 23. мај 2008. у 01:05
У теорији аутомата, детерминистички потисни аутомат је коначни детерминистички аутомат, који у свом раду користи стек.
Израз потисни се односи на операцију уношења података у стек, (енгл. push, потиснути), која додаје податак на врх стека.Термин "детерминистички потисни аутомат" се у теорији рачунарства односи на апстрактни математички аутомат који препознаје детерминистичке контекстно-независне језике. Детерминистички потисни аутомат је одређена верзија потисног аутомата.Интересантно је да детерминистички потисни аутомати спадају у праву подгрупу потисних аутомата ѕа разлику од детерминистички коначних аутомата и недетерминистички коначних аутомата.
Дефиниција
DPA 'M' се може дефинисати као уређена седморка:
где важи:
- је коначан скуп стања
- је коначан скуп улазних знакова(улазна азбука)
- је коначан скуп стековних симбола
- је почетно стаље
- је почетни симбол стека
- , where је скуп прихватних,финалних стања
- је функција прелаза где је
M је детерминистички ако задовољава оба следећа услова:
- За свако ,скуп садржи бар један елемент.
- За свако , ако је , тада је за свако
Постоје два могућа критеријума за прихватање знакова:прихватање праѕном потисном листом и прихватање завршним стањем.Ова два критеријума нису једнака за детерминистичке потисне аутомате иако јесу за недетерминистичке потисне аутомате.