Стековые машины, эквивалентность двухстековой машины МТ — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «== Стековая машина == <font face="Times" size="3"> Файл:StackMachine.png * Каждой конфигурации машины Тьюринга…»)
 
м (rollbackEdits.php mass rollback)
 
(не показано 29 промежуточных версий 6 участников)
Строка 1: Строка 1:
== Стековая машина ==
+
Стековая машина является обобщением [[Детерминированные автоматы с магазинной памятью | детерминированных МП-автоматов]] с использованием нескольких [[Стек | стеков]] вместо одного. <br>
<font face="Times" size="3">
+
{{Определение
[[Файл:StackMachine.png]]
+
|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>Q</tex> {{---}} множество состояний автомата;
 +
*<tex>s</tex> {{---}} стартовое состояние автомата;
 +
*<tex>T</tex> {{---}} множество допускающих состояний автомата;
 +
*<tex>z_0</tex> {{---}} маркер дна стека;
 +
*<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>\$</tex>. Тем самым бесконечно пустой хвост ленты виртуально присутствует в стековой машине.
+
== Эквивалентность двухстековой машины машине Тьюринга ==
 +
{{Теорема
 +
|statement=Язык <tex>L</tex> допускается [[Машина Тьюринга | машиной Тьюринга]] тогда и только тогда, когда он допускается двухстековой машиной.
 +
|proof=
 +
Для упрощения доказательства без умаления общности предположим, что вход для двухстековой машины заканчивается специальным символом <tex>\$</tex>, которого нет в исходном алфавите. <br>
 +
[[Изображение:SM.png|400px|thumb|center|Рис. 2. Представление ленты МТ двумя стеками и наоборот]]
 +
<tex>\Rightarrow</tex> <br>
 +
Докажем, что если язык <tex>L</tex> допускается машиной Тьюринга, то он допускается двухстековой машиной.
  
* Если слово допускается в машине Тьюринга <tex>\Rightarrow</tex> оно допускается и в стековой машине.  
+
Мы будем имитировать ленту МТ двумя стеками (Рис. 2). В первом стеке будет хранится кусок ленты слева от положения головки, во втором стеке {{---}} справа, включая текущий символ. Разумеется, куски ленты хранятся без бесконечных цепочек пробелов, окружающих значащие символы ленты.  
</font>
 
  
== Литература ==
+
Необходимо инициализировать стеки для того, чтобы их содержимое корректно отражало содержимое ленты МТ, поэтому строящаяся нами двухстековая машина сначала читает весь вход до конца (он помечен маркером <tex>\$</tex>) и кладёт каждый новый поступивший символ на первый стек. Затем она перебрасывает все значения из первого стека во второй, таким образом получив пустой первый стек (что соответствует бесконечной цепочке пробелов слева от головки МТ) и второй стек, содержащий весь вход (что соответствует положению всех значащих символов ленты МТ не левее головки МТ). После этого машина перейдёт в начальное (имитируемое) состояние МТ. <br>
<font face="Times" size="3">
+
 
*Н.К.Верещагин, А.Шень - "Вычислимые функции"
+
Теперь в каждый момент имитации мы будем знать текущий прочтённый головкой символ (им является вершина второго стека), и, соответственно, переход в МТ. <br>
</font>
+
 
 +
Действие "<tex>\leftarrow</tex>" МТ (сдвинуть головку влево) будем имитировать простым перекидыванием вершины первого стека на второй. Стоит обратить внимание на случай, когда первый стек перед действием был пуст, что говорило бы нам о том, что слева от головки бесконечная цепочка из пробелов. Поэтому такой переход имитируется добавлением на второй стек символа пробела и оставлением первого стека пустым. Аналогично делаются «сдвинуть головку вправо» и «остаться на месте».
 +
 
 +
После имитации действия соответствующего перехода в МТ двухстековая машина делает переход в имитируемое новое состояние МТ.
 +
 
 +
Допускающими состояниями двухстековой машины являются те, которые имитируют допускающие состояния МТ.
 +
 
 +
Таким образом, мы с помощью двухстековой машины сымитировали МТ.
 +
 
 +
<tex>\Leftarrow</tex> <br> Этот пункт доказательства аналогичен предыдущему. Содержимое двух стеков отображается лентой МТ так же, как и в предыдущем пункте (рис. 2). Снятие, например, с первого стека символа соответствует сдвигу куска ленты, соответствующего второму стеку, влево на одну позицию, что прекрасно умеет делать МТ. Положить символ на этот стек соответствует сдвигу куска ленты, соответствующего второму стеку, вправо на одну позицию, записи этого символа на место начального положения головки и сдвигу головки вправо на одну позицию (действие "положить цепочку на стек" аналогично последовательности действий "положить на стек один символ"). Операции со вторым стеком имитируются аналогично.
 +
}}
 +
 
 +
==См. также ==
 +
* [[Стек]]
 +
* [[Детерминированные автоматы с магазинной памятью]]
 +
* [[Машина Тьюринга]]
 +
* [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]]
 +
 
 +
== Источники информации ==
 +
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
 +
 
 +
 
 +
[[Категория: Теория вычислимости]]
 +
[[Категория: Вычислительные формализмы]]

Текущая версия на 19:28, 4 сентября 2022

Стековая машина является обобщением детерминированных МП-автоматов с использованием нескольких стеков вместо одного.

Определение:
[math]k[/math]-cтековой машиной называется набор A=[math]\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 [/math] [math] (Q \times (\Gamma^*)^k)\rangle[/math], где
  • [math]\Sigma[/math] — входной алфавит на ленте;
  • [math]\Gamma[/math] — стековый алфавит;
  • [math]Q[/math] — множество состояний автомата;
  • [math]s[/math] — стартовое состояние автомата;
  • [math]T[/math] — множество допускающих состояний автомата;
  • [math]z_0[/math] — маркер дна стека;
  • [math]\delta[/math] — функция переходов.
Рис. 1. k-стековая машина

На рис. 1 изображена k-стековая машина. С ленты последовательно считываются символы входного алфавита ([math]c_i[/math] — текущий считываемый символ). В каждом стеке с вершины снимается символ [math]x_i[/math], вместо него помещается строка [math]\alpha_i[/math] таким образом, чтобы первый символ строки находился на вершине стека, и делается переход в автомате в зависимости от считанного с ленты символа [math]c_i[/math] и снятых со стеков верхних значений [math]x_i[/math]. Возможен также и [math]\varepsilon\[/math]-переход.

Эквивалентность двухстековой машины машине Тьюринга

Теорема:
Язык [math]L[/math] допускается машиной Тьюринга тогда и только тогда, когда он допускается двухстековой машиной.
Доказательство:
[math]\triangleright[/math]

Для упрощения доказательства без умаления общности предположим, что вход для двухстековой машины заканчивается специальным символом [math]\$[/math], которого нет в исходном алфавите.

Рис. 2. Представление ленты МТ двумя стеками и наоборот

[math]\Rightarrow[/math]
Докажем, что если язык [math]L[/math] допускается машиной Тьюринга, то он допускается двухстековой машиной.

Мы будем имитировать ленту МТ двумя стеками (Рис. 2). В первом стеке будет хранится кусок ленты слева от положения головки, во втором стеке — справа, включая текущий символ. Разумеется, куски ленты хранятся без бесконечных цепочек пробелов, окружающих значащие символы ленты.

Необходимо инициализировать стеки для того, чтобы их содержимое корректно отражало содержимое ленты МТ, поэтому строящаяся нами двухстековая машина сначала читает весь вход до конца (он помечен маркером [math]\$[/math]) и кладёт каждый новый поступивший символ на первый стек. Затем она перебрасывает все значения из первого стека во второй, таким образом получив пустой первый стек (что соответствует бесконечной цепочке пробелов слева от головки МТ) и второй стек, содержащий весь вход (что соответствует положению всех значащих символов ленты МТ не левее головки МТ). После этого машина перейдёт в начальное (имитируемое) состояние МТ.

Теперь в каждый момент имитации мы будем знать текущий прочтённый головкой символ (им является вершина второго стека), и, соответственно, переход в МТ.

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

После имитации действия соответствующего перехода в МТ двухстековая машина делает переход в имитируемое новое состояние МТ.

Допускающими состояниями двухстековой машины являются те, которые имитируют допускающие состояния МТ.

Таким образом, мы с помощью двухстековой машины сымитировали МТ.

[math]\Leftarrow[/math]
Этот пункт доказательства аналогичен предыдущему. Содержимое двух стеков отображается лентой МТ так же, как и в предыдущем пункте (рис. 2). Снятие, например, с первого стека символа соответствует сдвигу куска ленты, соответствующего второму стеку, влево на одну позицию, что прекрасно умеет делать МТ. Положить символ на этот стек соответствует сдвигу куска ленты, соответствующего второму стеку, вправо на одну позицию, записи этого символа на место начального положения головки и сдвигу головки вправо на одну позицию (действие "положить цепочку на стек" аналогично последовательности действий "положить на стек один символ"). Операции со вторым стеком имитируются аналогично.
[math]\triangleleft[/math]

См. также

Источники информации

  • Хопкрофт Д., Мотвани Р., Ульман Д.Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)