40
правок
Изменения
Нет описания правки
== Стековая машина ==
[[Изображение:PDAk.png|620px|thumb|leftcenter|Рис. 1. k-стековая машина]]
Стековая машина является обобщением детерминированных МП-автоматов использованием нескольких стеков вместо одного. <br>
На рис. 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>-переход.
|proof=
Для упрощения доказательства без умаления общности предположим, что вход для двухстековой машины заканчивается специальным символом <tex>\$</tex>, которого нет в исходном алфавите. <br>
[[Изображение:SM.png|400px|thumb|leftcenter|Рис. 2. Представление ленты МТ двумя стеками и наоборот]]<tex>\Rightarrow)</tex> <br>
Докажем, что если язык <tex>L</tex> допускается машиной Тьюринга, то он допускается двухстековой машиной. <br>
Мы будем имитировать ленту МТ двумя стеками (Рис. 2). В первом стеке будет хранится кусок ленты слева от положения головки, во втором стеке — справа, включая текущий символ. Разумеется, куски ленты хранятся без бесконечных цепочек пробелов, окружающих значащие символы ленты. <br>
Таким образом, мы с помощью двухстековой машины сымитировали МТ.
<tex>\Leftarrow)</tex> <br> Этот пункт доказательства аналогичен предыдущему. Содержимое двух стеков отображается лентой МТ также, как и в предыдущем пункте (рис. 2). Снятие, например, с первого стека символа соответствует сдвигу куска ленты, соответствующего второму стеку, влево на одну позицию, что прекрасно умеет делать МТ. Положить символ на этот стек соответствует сдвигу куска ленты, соответствующего второму стеку, вправо на одну позицию, записи этого символа на место начального положения головки и сдвигу головки вправо на одну позицию (действие "положить цепочку на стек" аналогично последовательности действий "положить на стек один символ"). Операции со вторым стеком имитируются аналогично.
}}
==Источники==
