275
правок
Изменения
м
== Стековая машина ==
[[Изображение: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>-переход.
→Стековая машина
Стековая машина является обобщением [[Детерминированные автоматы с магазинной памятью | детерминированных МП-автоматов]] с использованием нескольких [[Стек | стеков]] вместо одного. <br>
{{Определение
|definition=
*<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>-переход.
== Эквивалентность двухстековой машины машине Тьюринга ==
