Пред. страница   . След. страница   Раздел   Содержание

__________________________________________________________________________________________________________

4.7. Магазинные Преобразователи.

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

4.7.1. Определение магазинного преобразователя.

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

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

4.7.2. Описание работы магазинного преобразователя.

    Для описания работы магазинного преобразователя необходимо дать его определение.

Определение:
Преобразователем с магазинной памятью (Мп) называется совокупность восьми 
                             объектов:

Мп={P, S, s₀, H, h₀, F, W, q},

где P - входной алфавит, состоящий из символов, записываемых на входную ленту; 

    W - выходной алфавит, содержащий символы, записываемые на выходную ленту; 

        H - магазинный алфавит, содержащий символы, записываемые и считываемые из     магазина; 

h₀ - маркер дна магазина, он принадлежит H; 

S - множество состояний преобразователя; 

s₀- начальное состояние из множества S; 

F - множество конечных состояний, представляющих собой подмножество S; 

j - функция переходов преобразователя, которая задает отображение, 

j: Sx{P È {$} x H Þ S x H* x W* .

Она может быть записана в функциональном виде:  

j(s, p, h) = (s', b, e), 

где h Î H,  p Î P,  b Î H*, e Î W* и s,s' Î S.

Определим конфигурацию Мп как четверку

(s, ac, rh, d),

где ac Î P*, rh Î H* и d Î W*.
Если такту работы преобразователя соответствует конфигурация (s, ac, rh , d) и определена функция переходов j(s, a, h) = (s', b, e), то происходит смена конфигурации, которую условимся записывать так:

(s, ac, rh, d) |-- (s', c, rb, de).

Последовательность сменяющих друг друга конфигураций, как обычно, обозначим символом |--*. В качестве начальной примем конфигурацию, которой соответствует заданная входная цепочка c на ленте, цепочка h₀I в магазине, начальное состояние s₀ и пустая цепочка на выходной ленте:
(s₀, c, h₀I, $).
    Конечной или заключительной конфигурацией назовем четверку (s_k, $, $, d), где s_k - одно из заключительных состояний из множества F, а d - выходная цепочка.

4.7.3.  Перевод определяемый преобразователем.

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

                                   (s₀, c, h₀I, $) |--* (s', $', $, d).

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

D(Mп) = {(x, y) | (s₀, c, h₀, $) |--* (s', $', $, y) & s' ÎF}

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

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

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

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

Пред. страница   . След. страница   Раздел   Содержание