Изменения

== Стековая машина ==является обобщением [[Изображение:PDAk.png|620px|thumb|leftДетерминированные автоматы с магазинной памятью |Рис. 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>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>Q</tex> — {{---}} множество состояний автомата;*<tex>s</tex> — {{---}} стартовое состояние автомата;*<tex>T</tex> — {{---}} множество допускающих состояний автомата;*<tex>z_0</tex> — {{---}} маркер дна стека;*<tex>\delta</tex> — {{---}} функция переходов.

|statement=Язык <tex>L</tex> допускается [[Машина Тьюринга | машиной Тьюринга ]] тогда и только тогда, когда он допускается двухстековой машиной.

Для упрощения доказательства без умаления общности предположим, что вход для двухстековой машины заканчивается специальным символом <tex>\$</tex>, которого нет в исходном алфавите (аналог пробела в МТ). <br>[[Изображение:SM.png|400px|thumb|leftcenter|Рис. 2. Представление ленты МТ двумя стекамии наоборот]]<tex>\Rightarrow)</tex> <br>Докажем, что если язык <tex>L</tex> допускается машиной Тьюринга, то он допускается двухстековой машиной. <br> Мы будем имитировать ленту МТ двумя стеками (Рис. 2). В первом стеке будет хранится кусок ленты слева от положения головки, во втором стеке — {{---}} справа, включая текущийсимвол. Разумеется, куски ленты хранятся без бесконечных цепочек пробелов, окружающих значащие символы ленты. <br>Исходя из необходимости Необходимо инициализировать стеки для того, чтобы их содержимое корректно отражало содержимое ленты МТ, поэтому строящаяся нами двухстековая машина сначала читает весь вход до конца (он помечен маркером <tex>\$</tex>) и кладёт каждый новый поступивший символ на первый стек. Затем наша машина она перебрасывает все значения из первого стека во второй, таким образом получив пустой первый стек (что соответствует бесконечной цепочке пробелов слева от головки МТ) и второй стек, содержащий весь вход (что соответствует положению всех значащих символов ленты МТ не левее от головки МТ). После этого машина перейдёт в начальное (имитируемое) состояние МТ. <br> 

 Действие "<tex>\leftarrow</tex>" МТ (сдвинуть головку влево) будем имитировать простым перекидыванием вершины первого стека на второй. Стоит обратить внимание на случай, когда первый стек перед действием был пуст, что говорило бы нам о том, что слева от головки бесконечная цепочка из пробелов. Поэтому такой переход имитировался имитируется добавлением на второй стек символа пробела и оставлением первого стека пустым. Аналогично делаются "сдвинуть «сдвинуть головку вправо" вправо» и "остаться «остаться на месте"месте».  После имитации действия соответствующего перехода в МТ, двухстековая машина делает переход в имитируемое новое состояние МТ. <br> Допускающими состояниями двухстековой машины являются те, которые имитируют допускающие состояния МТ. <br> 

[[Изображение:SMM.png|400px|thumb|left|Рис. 3. Представление двух стеков лентой МТ]]<tex>\Leftarrow)</tex> Докажем, что если язык <texbr>L</tex> допускается двухстековой машиной, то он допускается машиной ТьюрингаЭтот пункт доказательства аналогичен предыдущему. <br> Двухстековую машину можно сымитировать трехленточной Содержимое двух стеков отображается лентой МТ так же, как и в предыдущем пункте (Рисрис. 32). На первой ленте будет записан входСнятие, например, с первого стека символа соответствует сдвигу куска ленты, соответствующего второму стеку, влево на одну позицию, вторая лента будет имитировать первый что прекрасно умеет делать МТ. Положить символ на этот стексоответствует сдвигу куска ленты, соответствующего второму стеку, вправо на одну позицию, третья — второйзаписи этого символа на место начального положения головки и сдвигу головки вправо на одну позицию (действие "положить цепочку на стек" аналогично последовательности действий "положить на стек один символ"). <br>Стеки Операции со вторым стеком имитируются Конечный автомат для МТ получим из двухстековой машины следующей заменой действия на переходе:аналогично.