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

Садржај обрисан Садржај додат

Инлајн

Верзија на датум 7. јун 2008. у 12:14

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

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

Дефиниција

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

$M=(\Sigma \,,\mathbb {Q} ,\Gamma \,,i\,,Z_{0}\,,K\,,\Delta \,)$ где важи:

$\Sigma \,$ је коначан скуп улазних знакова(улазна азбука)
$Q\,$ је азбука стања
$\Gamma \,$ је азбука потисне листе
$i\,\in Q\,$ је почетно стање
$Z_{0}\,\in \Gamma \,$ је почетни симбол потисне листе
$K\,\subseteq Q\times \Gamma ^{*}$ , скуп завршних конфигурација
$\Delta \,\subseteq Q\,\times (\Sigma \,\cup \left\{\epsilon \,\right\})\times \Gamma \,\times Q\times \Gamma ^{*}$ је скуп правила прелаза.

Петорка $(q,a,Z,r,\gamma )\in \Delta$ се назива правило, а ако је $a=\epsilon \$ онда $\epsilon$ -правило.

Конфигурација потисног аутомата М је тројка $(q,\omega ,\gamma )\in Q\times \Sigma ^{*}\times \Gamma ^{*}$ где је $\omega \$ реч коју ће аутомат прочитати, а $(q,\gamma )$ унутрашња конфигурација аутомата (први карактер ниске $\gamma \$ је на врху потисне листе).

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

За свако $q\in Q,a\in \Sigma \cup \left\{\epsilon \right\},x\in \Gamma$ , скуп $\Delta (q,a,x)\,$ садржи бар један елемент.
За свако $q\in Q,x\in \Gamma$ , ако је $\Delta (q,\epsilon ,x)\not =\emptyset \,$ , тада је $\Delta \left(q,a,x\right)=\emptyset$ за свако $a\in \Sigma$

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

Овај чланак везан за рачунарство је клица. Можете допринети Википедији тако што ћете га проширити.

@@ Ред 19: / Ред 19: @@
 *<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,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> \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, 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>
 Постоје два могућа критеријума за прихватање знакова:прихватање празном потисном листом и прихватање завршним стањем. Ова два критеријума нису једнака за детерминистичке потисне аутомате иако јесу за недетерминистичке потисне аутомате.