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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
== Стековая машина ==
 
== Стековая машина ==
Стековая машина является обобщением детерминированных МП-автоматов использованием <tex>k</tex> стеков вместо одного. <br>
+
Стековая машина является обобщением детерминированных МП-автоматов использованием нескольких стеков вместо одного. <br>
 
На рис. 1 изображена '''стековая машина'''. С ленты последовательно считываются символы входного алфавита (<tex>c_i</tex> — текущий считываемый символ). Для каждого стека с вершины снимается символ <tex>x_i</tex>. Вместо него помещается строка <tex>\alpha_i</tex> таким образом, чтобы первый символ строки находился на вершине стека.
 
На рис. 1 изображена '''стековая машина'''. С ленты последовательно считываются символы входного алфавита (<tex>c_i</tex> — текущий считываемый символ). Для каждого стека с вершины снимается символ <tex>x_i</tex>. Вместо него помещается строка <tex>\alpha_i</tex> таким образом, чтобы первый символ строки находился на вершине стека.
 
{{Определение
 
{{Определение

Версия 11:29, 28 декабря 2011

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

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

Определение:
Стековой машиной с [math]k[/math] магазинами называется набор 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] — функция переходов.