Пример 2 2 : x {a, b} * переводит в y = (ab) n Например, 2 (aababb ) = ababab. ДМП P = ({q 0, q z }, {a, b, }, {Z, a, b}, {a, b}, F, q 0, Z, {q z }) Функция переходов вида: F(q 0, X, Z) = {(q 0, XZ, )}, X {a, b}; F(q 0,, Z) = {(q z, Z, )}; F(q 0, X, X) = {(q 0, XX, )}, X {a, b}; F(q 0, X, Y)={(q 0,, ab)}, X {a, b}, Y {a, b}, X Y.
Перевод цепочки aababb Q Стек Вход Выход q0q0 Z aababb q0q0 Za ababb q0q0 Zaa babb q0q0 Za abb ab q0q0 Zaa bb ab q0q0 Za b abab q0q0 Z ababab qzqz Z ababab