275
правок
Изменения
м
→Недетерминированный автомат с магазинной памятью
{{Определение
|definition= '''Автомат с магазинной памятью''' (автомат со стеком, англ. ''pushdown automaton'') {{---}} это набор <tex>A=\langle\Sigma,\Gamma,Q,s\in Q, T \subset Q, z_0 \in \Gamma, \delta : Q \times \Sigma \cup \{\varepsilon\} \times \Gamma \rightarrow 2^Q \times \Gamma^*\rangle</tex>, где
*<tex>\Sigma</tex> {{---}} входной алфавит на ленте;,*<tex>\Gamma</tex> {{---}} стековый алфавит;,*<tex>Q</tex> {{---}} множество состояний автомата;,*<tex>s</tex> {{---}} стартовое состояние автомата;,*<tex>T</tex> {{---}} множество допускающих состояний автомата;,*<tex>z_0</tex> {{---}} маркер дна стека;,
*<tex>\delta</tex> {{---}} функция переходов.
}}
[[Изображение:PDA.png|250px|thumb|left|Рис. 1. Автомат с магазинной памятью]]
На рис. 1 изображен автомат с магазинной памятью. С ленты последовательно считываются символы входного алфавита (<tex>c_i</tex> {{---}} текущий считываемый символ). Символ <tex>x</tex> снимается с вершины стека. Вместо него помещается строка <tex>\alpha</tex> таким образом, чтобы первый символ строки находился на вершине стека.
