Изменения

Перейти к: навигация, поиск
Нет описания правки
== Стековая машина ==
[[Изображение:PDAk.png|thumb|left|Рис. 1. Стековая машина с k стеками]]
Стековая машина является обобщением детерминированных МП-автоматов использованием нескольких стеков вместо одного. <br>
На рис. 1 изображена '''стековая машина'''. С ленты последовательно считываются символы входного алфавита (<tex>c_i</tex> — текущий считываемый символ). Для каждого стека с вершины снимается символ <tex>x_i</tex>. Вместо него помещается строка <tex>\alpha_i</tex> таким образом, чтобы первый символ строки находился на вершине стека.
*<tex>\delta</tex> — функция переходов.
}}
 
== Эквивалентность двухстековой машины машине Тьюринга ==
40
правок

Навигация