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

Нема описа измене
Детерминистички потисни аутомат 'M' се може дефинисати као уређена седморка:
 
<math>M=(Q\Sigma\,, \Sigma\,Q, \Gamma\,, q_0i\,, Z_0\,, AK\,, \deltaDelta\,)</math>
где важи:
 
*<math>Q\Sigma\,</math> је коначан скуп стањаулазних знакова(улазна азбука)
*<math>\Sigma Q\,</math> је коначаназбука скуп улазних знакова(улазна азбука)стања
*<math>\Gamma\,</math> је коначанје скупазбука стековнихпотисне симболалисте
*<math>q_0i\,\in Q\,</math> је почетно стаљестање
*<math>Z_0\,\in\Gamma\,</math> је почетни симбол стекапотисне листе
*<math>AK\,\subseteq Q \,</math>, где јеtimes \Gamma <math>A^{*}</math>, скуп прихватних, завршних стањаконфигурација
:*<math>\deltaDelta\,:(\subseteq Q\, \times ( \Sigma\, \cup \left \{ \lambdaepsilon\, \right \} ) \times \Gamma\,) \longrightarrowtimes Q \times \Gamma ^{*}</math> је скуп правила прелаза.
*<math>\delta\,</math> је функција прелаза где је
 
:<math>\delta\,:(Q\, \times ( \Sigma\, \cup \left \{ \lambda\, \right \} ) \times \Gamma\,) \longrightarrow Q \times \Gamma ^{*}</math>
''M'' је детерминистички ако задовољава оба следећа услова:
* За свако <math> q \in Q, a \in \Sigma \cup \left \{ \lambdaepsilon \right \}, x \in \Gamma</math>,скуп <math>\deltaDelta(q,a,x)\,</math> садржи бар један елемент.
* За свако <math> q \in Q, x \in \Gamma</math>, ако је <math>\deltaDelta(q, \lambdaepsilon, x) \not= \emptyset\,</math>, тада је <math>\deltaDelta\left( q,a,x \right) = \emptyset</math> за свако <math>a \in \Sigma</math>
Постоје два могућа критеријума за прихватање знакова:прихватање празном потисном листом и прихватање завршним стањем. Ова два критеријума нису једнака за детерминистичке потисне аутомате иако јесу за недетерминистичке потисне аутомате.
 
62

измене