Преобразователи с магазинной памятью

Рассмотрим важный класс абстрактных устройств, называемых преобразователями с магазинной памятью. Эти преобразователи получаются из автоматов с магазинной памятью, если к ним добавить выход и позволить на каждом шаге выдавать выходную цепочку.

Преобразователем с магазинной памятью (МП-преоб- разователем) называется восьмерка , где все символы имеют тот же смысл, что и в определении МП-автомата, за исключением того, что - конечный выходной алфавит, а D - отображение множества в множество конечных подмножеств множества .

Определим конфигурацию преобразователя P как четверку (q, x, u, y), где - состояние, - цепочка на входной ленте, - содержимое магазина, - цепочка на выходной ленте, выданная вплоть до настоящего момента.

Если множество D(q, a, Z) содержит элемент (r, u, z), то будем писать для любых , и : Рефлексивно - транзитивное замыкание отношения будем обозначать .

Цепочку y назовем выходом для x, если для некоторых и . Переводом (или трансляцией), определяемым МП-преобразователем P (обозначается ), назовем множество

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

1. для всех и множество D(q, a, Z) содержит не более одного элемента,

2. если , то для всех .

Пример 5.1. Рассмотрим перевод отображающий каждую цепочку , в которой число вхождений символаa равно числу вхождений символа b, в цепочку y = (ab)ⁿ, где n - число вхождений a или b в цепочку x. Например, .

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