1632
правки
Изменения
м
== Стековая машина ==
[[Изображение:PDAk.png|620px|thumb|center|Рис. 1. k-стековая машина]]
На рис. 1 изображена '''k-стековая машина'''. С ленты последовательно считываются символы входного алфавита (<tex>c_i</tex> {{---}} текущий считываемый символ). В каждом стеке с вершины снимается символ <tex>x_i</tex>, вместо него помещается строка <tex>\alpha_i</tex> таким образом, чтобы первый символ строки находился на вершине стека, и делается переход в автомате в зависимости от считанного с ленты символа <tex>c_i</tex> и снятых со стеков верхних значений <tex>x_i</tex>. Возможен также и <tex>\varepsilon\</tex>-переход.
rollbackEdits.php mass rollback
Стековая машина является обобщением [[Детерминированные автоматы с магазинной памятью | детерминированных МП-автоматов]] с использованием нескольких [[Стек | стеков]] вместо одного. <br>
{{Определение
|definition=
*<tex>\delta</tex> {{---}} функция переходов.
}}
[[Изображение:PDAk.png|620px|thumb|center|Рис. 1. k-стековая машина]]
На рис. 1 изображена '''k-стековая машина'''. С ленты последовательно считываются символы входного алфавита (<tex>c_i</tex> {{---}} текущий считываемый символ). В каждом стеке с вершины снимается символ <tex>x_i</tex>, вместо него помещается строка <tex>\alpha_i</tex> таким образом, чтобы первый символ строки находился на вершине стека, и делается переход в автомате в зависимости от считанного с ленты символа <tex>c_i</tex> и снятых со стеков верхних значений <tex>x_i</tex>. Возможен также и <tex>\varepsilon\</tex>-переход.
== Эквивалентность двухстековой машины машине Тьюринга ==
<tex>\Leftarrow</tex> <br> Этот пункт доказательства аналогичен предыдущему. Содержимое двух стеков отображается лентой МТ так же, как и в предыдущем пункте (рис. 2). Снятие, например, с первого стека символа соответствует сдвигу куска ленты, соответствующего второму стеку, влево на одну позицию, что прекрасно умеет делать МТ. Положить символ на этот стек соответствует сдвигу куска ленты, соответствующего второму стеку, вправо на одну позицию, записи этого символа на место начального положения головки и сдвигу головки вправо на одну позицию (действие "положить цепочку на стек" аналогично последовательности действий "положить на стек один символ"). Операции со вторым стеком имитируются аналогично.
}}
==См. также ==
* [[Стек]]
* [[Детерминированные автоматы с магазинной памятью]]
* [[Машина Тьюринга]]
* [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]]
== Источники информации ==
