Магазинные преобразователи. Определение магазинного преобразователя. Перевод, определяемый преобразователем

Подобные устройства позваляют строить по заданной входной цепочки соответствующую ей выходную цепочку. Множество таких пар цепочек называют переводом или трансляцией, допускаемым магазинным преобразователем. Для того чтобы построить преобразователь необходимо заранее знать какой перевод он должен выполнять. Кроме того, преобразователь можно построить не для любого перевода, а только для такого, который может быть описан с помощью простой СУ-схемы. Для построения детерминированного преобразователя необходимо еще, чтобы входная грамматика заданной СУ-схемы пораждала детерминированный язык.

Магазинный преобразователь (Мп) отмагазинного автоматаналичием дополнительной выходной ленты, на которую записывается выходная цепочка. Схему магазинного преобразователяможно изобразить следующим образом:

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

Цепочку d назовем выходом для цепочки c, если существует последовательность конфигураций, первой из которых является начальная конфигурация с заданной входной цепочкой c, а последней – заключительная конфигурация с выходной цепочкой d:

(s0, c, h0I, $) |--* (s', $', $, d).

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

D(Mп) = {(x, y) | (s0, c, h0, $) |--* (s', $', $, y) & s' ОF}

Используя последнее определение, можно определить возможность построения преобразователя, реализующего заданный перевод в виде следующего утверждения.

Для каждой простой СУ-схемы перевода Т = {Va, Vтвх, Vтвых, Q, I} можно построить такой Мп магазинный преобразователь, что D(Т) = D(Мп).

Приведенное утверждение говорит о возможности построения преобразователя, но не гарантирует получение детерминированного преобразователя, который может быть получен при выполнении следующих условий:

Для каждой простой СУ - схемы перевода Т, входная грамматика которой принадлежит классу LL(1) - грамматик, можно построить такой детерминированный магазинный преобразовательМп, что перевод, оеделяемый преобразователем, совпадает с переводом, задаваемым СУ - схемой Т.