Преобразователи с магазинной памятью
Рассмотрим важный класс абстрактных устройств, называемых преобразователями с магазинной памятью. Эти преобразователи получаются из автоматов с магазинной памятью, если к ним добавить выход и позволить на каждом шаге выдавать выходную цепочку.
Преобразователем с магазинной памятью (МП-преобразователем) называется восьмерка P = (Q, T,


того, что



в множество конечных подмножеств множества Q Ч


Определим конфигурацию преобразователя P как четверку (q, x, u, y), где q






Если множество D(q, a, Z) содержит элемент (r, u, z), то будем писать (q, ax, Zw, y)








Цепочку y назовем
выходом для x, если (q0, x, Z0, e)






Будем говорить, что МП-преобразователь P является детерминированным (ДМП-преобразователем), если выполняются следующие условия:







то D(q, a, Z) =


Пример5.1. Рассмотрим перевод



Этот перевод может быть реализован ДМП-преобразователем P = ({q0, qf}, {a, b, $}, {Z, a, b}, {a, b}, D, q0, Z, {qf}) c функцией переходов:
D(q0, X, Z) = {(q0, XZ, e)}, X

D(q0, $, Z) = {(qf, Z, e)},
D(q0, X, X) = {(q0, XX, e)}, X

D(q0, X, Y ) = {(q0, e, ab)}, X


