17.Соответствие между т-грамматики и су-схемы.

Построение транслирующей грамматики по СУ - схеме.

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

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

Утверждение. Для каждой простой СУ-схемы Т можно построить транслирующую грамматику ГТ такую, что переводы, порождаемые СУ - схемой и Т - грамматикой, совпадают. C(T) = C(ГТ)

Чтобы показать справедливость этого утверждения, опишем способ построения Т - грамматики по заданной СУ - схеме. Допустим, что задана СУ - схема Т = {V_твх, V_твых,V_a,Q,I}и требуется построить Т - грамматику

Г~ = {V'_твх,V'_твых,V'_a,R,I}. Для того чтобы получить тот же самый перевод, необходимо, чтобы V_твх = V_твх', V_твых = V_твх', V_a = V_a'. Рассмотрим преобразование правила из множества Q СУ - схемы A╝ , , где цепочки  = x_оA_ох₁А₁...x_nA_n и  = y_оA_оу₁A₁...у_nA_n, и поставим в соответствие этому правилу правило грамматики в виде: А ╝x_оу_оA_ох₁у₁A₁...x_ny_nA_n. Это можно сделать всегда, поскольку СУ - схема - простая и в каждом ее правиле используются одни и те же нетерминалы в одном и том же порядке. Рассмотренное построение обеспечивает включение во входную цепочку выходных символов цепочки, порождаемой СУ-схемой. Следовательно, каждый шаг вывода в Т - грамматике будет добавлять к выводимой цепочке те же символы, что и СУ - схема добавляет к выходной цепочке. Применение описанных положений рассмотрим на примере построения Т - грамматики по СУ - схеме Т_4.4. Используя фигурные скобки для представления выходных символов и выполняя пре-образование, получаем грамматику Г_4.1: R = {<A> ╝ x{x}, <A> ╝ (<B>), <B> ╝ <A><C>, <C> ╝ +<A>{+}<C>, <C> ╝ $ }.

Перевод цепочки ((x+x)+x) с применением правил построенной грамматики может быть получен с помощью следующего вывода: <A> ==> <A><C> ==> (<B>)<C> ==> (<A><C>)<C> ==> ((<B>)<C>)<C> ==> ((<A><C>)<C>)<C> ==> ((x{x}<C>)<C> ==> ((x{x}+<A>{+}<C>)<C>)<C> ==> ((x{x}+x{x}{+}<C>)<C>)<C> ==>((x{x}+x{x}{+})<C>)<C> ==> ((x{x}+x{x}{+})+<A>{+}<C>)<C> ==> ((x{x}+x{x}{+})+x{x}{+}<C>)<C> ==> ((x{x}+x{x}{+})+x{x}{+})<C> ==> ((x{x}+x{x}{+})+x{x}{+}).

Исключая из полученной цепочки вначале выходные, а затем входные символы, получаем выводимую пару ((x+x)+x,{x}{x}{+}{x}{+}),

которая совпадает с результатом вывода в заданной СУ - схеме.

18. Определение магазинного нисходящего преобразователя и его работа.

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

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

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

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

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

Определение: Преобразователем с магазинной памятью (Мп) называется совокупность восьми объектов: Мп={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', , ),  где h  H, p  P,   H*,   W* и s,s'  S.

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

(s, a, h, ),где a  P*, h  H* и   W*. Если такту работы преобразователя соответствует конфигурация (s, a, h , ) и определена функция переходов (s, a, h) = (s', , ), то происходит смена конфигурации, которую условимся записывать так: (s, a, h, ) |-- (s', , , ).

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