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