Изменения
→Недетерминированный автомат с магазинной памятью
{{Определение
|definition= Автомат с магазинной памятью (автомат со стеком, pushdown automaton) --- это набор A=<tex>\langle\Sigma,\Gamma,Q,s\in Q, T \subset Q, z_0 \in \Gamma, \delta : Q \times \Sigma \cup \{\varepsilon\} \times \Gamma \rightarrow \cal P</tex><tex>(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> {{--- }} функция переходов.
}}
