4.3.1. Определение магазинного преобразователя.
Магазинный преобразователь (Мп)от магазинного автомата наличием дополнительной выходной ленты, на которую записывается выходная цепочка. Схему магазинного преобразователя можно изобразить следующим образом:
В этой схеме входная головка в каждом такте работы может оставаться на месте или двигаться на одну позицию вправо. Выходная головка также может быть неподвижной или смещаться вправо, а головка магазинной ленты может перемещаться в обоих направлениях, причем такие перемещения связаны с операциями записи и чтения.
4.3.2. Описание работы магазинного преобразователя.
Для описания работы магазинного преобразователя необходимо дать его определение.
|
Определение:Преобразователем с магазинной памятью (Мп) называется совокупность восьми объектов: Мп={P, S, s0, H, h0, F, W, q}, где P- входной алфавит, состоящий из символов, записываемых на входную ленту; W- выходной алфавит, содержащий символы, записываемые на выходную ленту; H- магазинный алфавит, содержащий символы, записываемые и считываемые из магазина; h0- маркер дна магазина, он принадлежитH; S- множество состояний преобразователя; s0- начальное состояние из множестваS; F- множество конечных состояний, представляющих собой подмножествоS; - функция переходов преобразователя, которая задает отображение, : Sx{P {$} x H S x H* x W* . Она может быть записана в функциональном виде: (s,p,h) = (s',,), где hH,pP,H*,W*иs,s' S. |
Определим конфигурацию Мпкак четверку
(s,a,h,),
где aP*,hH*иW*. Если такту работы преобразователя соответствует конфигурация (s,a,h ,) и определена функция переходов(s,a,h) = (s',,), то происходит смена конфигурации, которую условимся записывать так:
(s,a, h,) |-- (s',,, ).
Последовательность сменяющих друг друга конфигураций, как обычно, обозначим символом |--*. В качестве начальной примем конфигурацию, которой соответствует заданная входная цепочка на ленте, цепочкаh0I в магазине, начальное состояниеs0и пустая цепочка на выходной ленте: (s0,,h0I,$). Конечной или заключительной конфигурацией назовем четверку (sk, $, $, ), гдеsk- одно из заключительных состояний из множестваF, а - выходная цепочка.
4.3.3. Перевод определяемый преобразователем.
|
Определение. Цепочкуназовем выходом для цепочки, если существует последовательность конфигураций, первой из которых является начальная конфигурация с заданной входной цепочкой, а последней – заключительная конфигурация с выходной цепочкой: (s0, , h0I, $) |--* (s', $', $, ). Определение. Переводом, определяемым преобразователем с магазинной памятью Мп, назовем множество пар, состоящих из входных и соответствующих им выходных цепочек. D(Mп) = {(x,y) | (s0,,h0,$) |--* (s',$',$,y) & s' F} |
Используя последнее определение, можно определить возможность построения преобразователя, реализующего заданный перевод в виде следующего утверждения.
|
Утверждение. Для каждой простой СУ-схемы перевода Т = {Va,Vтвх,Vтвых,Q,I} можно построить такойМпмагазинный преобразователь, чтоD(Т) =D(Мп). |
Приведенное утверждение говорит о возможности построения преобразователя, но не гарантирует получение детерминированного преобразователя, который может быть получен при выполнении следующих условий:
|
Утверждение. Для каждой простой СУ - схемы перевода Т, входная грамматика которой принадлежит классу LL(1) - грамматик, можно построить такойдетерминированный магазинный преобразовательМп, что перевод, оеделяемый преобразователем, совпадает с переводом, задаваемым СУ - схемой Т . |