36
правок
Изменения
→См. также
{{Определение
|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>-переход.
== Эквивалентность двухстековой машины машине Тьюринга ==
{{Теорема
|statement=Язык <tex>L</tex> допускается [[Машина Тьюринга | машиной Тьюринга ]] тогда и только тогда, когда он допускается двухстековой машиной.
|proof=
Для упрощения доказательства без умаления общности предположим, что вход для двухстековой машины заканчивается специальным символом <tex>\$</tex>, которого нет в исходном алфавите. <br>
<tex>\Leftarrow</tex> <br> Этот пункт доказательства аналогичен предыдущему. Содержимое двух стеков отображается лентой МТ так же, как и в предыдущем пункте (рис. 2). Снятие, например, с первого стека символа соответствует сдвигу куска ленты, соответствующего второму стеку, влево на одну позицию, что прекрасно умеет делать МТ. Положить символ на этот стек соответствует сдвигу куска ленты, соответствующего второму стеку, вправо на одну позицию, записи этого символа на место начального положения головки и сдвигу головки вправо на одну позицию (действие "положить цепочку на стек" аналогично последовательности действий "положить на стек один символ"). Операции со вторым стеком имитируются аналогично.
}}
==См. также ==
* [[Стек]]
* [[Детерминированные автоматы с магазинной памятью]]
* [[Машина Тьюринга]]
* [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]]
== Источники информации ==
