40
правок
Изменения
Нет описания правки
{{Определение
|definition=
<tex>k</tex>-cтековой машиной называется набор A=<tex>\langle\Sigma, \Gamma, Q, s\in Q, T \subset Q, z_0 \in \Gamma, \delta : Q \times \Sigma \cup \{\varepsilon\} \times \Gamma^k \rightarrow \cal P </tex> <tex> (Q \times (\Gamma^*)^k)\rangle</tex>, где
*<tex>\Sigma</tex> — входной алфавит на ленте;
*<tex>\Gamma</tex> — стековый алфавит;
<tex>\Leftarrow)</tex> Этот пункт доказательства аналогичен предыдущему. Содержимое двух стеков отображается лентой МТ также, как и в предыдущем пункте (рис. 2). Снятие, например, с первого стека символа соответствует сдвигу куска ленты, соответствующего второму стеку, влево на одну позицию, что прекрасно умеет делать МТ. Положить символ на этот стек соответствует сдвигу куска ленты, соответствующего второму стеку, вправо на одну позицию, записи этого символа на место начального положения головки и сдвигу головки вправо на одну позицию (действие "положить цепочку на стек" аналогично последовательности действий "положить на стек один символ"). Операции со вторым стеком имитируются аналогично.
}}
==Источники==
*Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений, 2-е изд.. : Пер. с англ. — М. : Издательский дом "Вильямс", 2002.
