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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 2: Строка 2:
 
[[Изображение:PDAk.png|620px|thumb|left|Рис. 1. Стековая машина с k стеками]]
 
[[Изображение:PDAk.png|620px|thumb|left|Рис. 1. Стековая машина с k стеками]]
 
Стековая машина является обобщением детерминированных МП-автоматов использованием нескольких стеков вместо одного. <br>
 
Стековая машина является обобщением детерминированных МП-автоматов использованием нескольких стеков вместо одного. <br>
На рис. 1 изображена '''k-стековая машина'''. С ленты последовательно считываются символы входного алфавита (<tex>c_i</tex> — текущий считываемый символ). Для каждого стека с вершины снимается символ <tex>x_i</tex>. Вместо него помещается строка <tex>\alpha_i</tex> таким образом, чтобы первый символ строки находился на вершине стека.
+
На рис. 1 изображена '''k-стековая машина'''. С ленты последовательно считываются символы входного алфавита (<tex>c_i</tex> — текущий считываемый символ). Для каждого стека с вершины снимается символ <tex>x_i</tex>, вместо него помещается строка <tex>\alpha_i</tex> таким образом, чтобы первый символ строки находился на вершине стека и делается переход в автомате в зависимости от считанного с ленты символа <tex>c_i</tex> и снятых со стеков верхних значений <tex>x_i</tex>.
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Строка 19: Строка 19:
 
|statement=Язык <tex>L</tex> допускается машиной Тьюринга тогда и только тогда, когда он допускается двухстековой машиной.
 
|statement=Язык <tex>L</tex> допускается машиной Тьюринга тогда и только тогда, когда он допускается двухстековой машиной.
 
|proof=
 
|proof=
Для упрощения доказательства без умаления общности предположим, что вход для двухстековой машины заканчивается специальным символом <tex>\$</tex>, которого нет в исходном алфавите (аналог пробела в МТ).
+
Для упрощения доказательства без умаления общности предположим, что вход для двухстековой машины заканчивается специальным символом <tex>\$</tex>, которого нет в исходном алфавите (аналог пробела в МТ). <br>
 +
<tex>\Rightarrow)</tex>
 +
Докажем, что если язык <tex>L</tex> допускается машиной Тьюринга, то он допускается двухстековой машиной. <br>
 +
[[Изображение:SM.png|400px|thumb|left|Рис. 2. Представление ленты МТ двумя стеками]]
 +
Мы будем имитировать ленту МТ двумя стеками (см. Рис. 2). В первом стеке будет хранится кусок ленты слева от положения головки, во втором стеке — справа. Разумеется, куски ленты хранятся без бесконечных цепочек пробелов, окружающих значащие символы ленты. <br>
 +
Исходя из необходимости инициализировать стеки для того, чтобы их содержимое отражало ленту МТ, строящаяся нами двухстековая машина сначала читает весь вход до конца (он помечен маркером <tex>\$</tex>) и кладёт каждый новый поступивший символ на первый стек.
 +
 
 +
<tex>\Leftarrow)</tex>
 
}}
 
}}

Версия 12:23, 28 декабря 2011

Стековая машина

Рис. 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]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 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] — функция переходов.


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

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

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

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

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

[math]\Leftarrow)[/math]
[math]\triangleleft[/math]