Стековые машины, эквивалентность двухстековой машины МТ

Материал из Викиконспекты
Перейти к: навигация, поиск

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

Рис. 1. Стековая машина с k стеками

Стековая машина является обобщением детерминированных МП-автоматов использованием нескольких стеков вместо одного.
На рис. 1 изображена k-стековая машина. С ленты последовательно считываются символы входного алфавита ([math]c_i[/math] — текущий считываемый символ). Для каждого стека с вершины снимается символ [math]x_i[/math]. Вместо него помещается строка [math]\alpha_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] — функция переходов.


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

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