Доопределим функцию reduction на некоторых разбиениях цепочек множества {р(а)\а е SG}, полагая

reduction(p(u1,..., um)) = {p(x)\x е reduction(u1,..., um)}.

Тогда наша обычная техника редуцирования позволяет доказать следующее утверждение.

Лемма 13. Пусть а е SG - терминальная структура и 8а - множество команд, построенных по р(а) по данным выше правилам (1)-(6). Тогда 8а входит в множество команд преобразователя M(G) □

Понятия дуги, маршрута и т. пр., введенные для магазинного автомата, очевидным образом обобщаются на случай преобразователя с магазинной памятью. Это дает нам право применять введенные в главе 1 термины и обозначения к преобразователю M(G).

Обсудим особенности маршрутов преобразователя M(G). В этом обсуждении будет полезным

Пусть G = (N, Е, P, S) - бесконтекстная грамматика, D - дерево вывода некоторой цепочки языка L(G). Тогда назовем (D,j)-кроной крону ([Aho -Ullman 72], стр. 165) дерева, полученного из D удалением всех вершин, уровень которых больше j.

Заметим, что (D,j)крона является сентенциальной формой, не обязательно правовыводимой.

Только команда вида (2) может перевести преобразователь M(G) в заключи тельное состояние. Следовательно, его успешный маршрут нейтрален и имеет вид

(7)поТопп,

где дуги п0, п и П определяются командами вида (1), (6) и (2) соответственно, То есть нейтральный маршрут.

Из вида команд преобразователя M(G) следует также

Лемма 14. Каждый собственный непустой нейтральный участок успешного маршрута преобразователя M(G) имеет вид

(8)Т1п1.. .Tkпкпk+l,

где k > 1, для 1 < i < k Т является нейтральным маршрутом, дуга п определяется командой какоголибо из видов (3), (4), (6), пк+1 - командой вида (5). Если следующая за пк+1 дуга пишет на выходной ленте номер p и р,(пк+1) = -7, то 7 = р(ХР1. ..ХрПр) ITJ

Назовем дуги п1,...,пк в разложении (8) собственного нейтрального участка успешного маршрута преобразователя M(G) каркасными дугами данного участка. Назовем дуги п0, п в разложении (7) каркасными дугами данного успешного маршрута.

Пусть Т - успешный маршрут преобразователя M(G). Определим рекурсивно уровень каркасных дуг нейтральных участков маршрута Т:

1)каркасные дуги маршрута Т - это дуги уровня 1;

2)пусть j > 1 и Т - такой непустой нейтральный участок маршрута Т, что непосредственно за ним в Т следует дуга уровня j - 1; тогда назовем каркасные дуги участка Т дугами уровня j.

Пусть X е V U {±}, a,b G Е U {±}, r = (p,j) G positions(X). Пусть Z есть прогноз, состоящий либо из одной роли [p, j, a], либо из двух ролей [p, j, a] и [q, 0, b], где (q, 0) G positions(A). Тогда полагаем symb(Z) = symb(r).

Пусть T - успешный маршрут преобразователя M(G). Пусть для некоторого k > 1 T = Tj0nj1Tj1... iyjkTjk, где 7Tji,..., njk есть все дуги маршрута T, уровень которых не превосходит j. Тогда назовем (T, j)-формой цепочку

form(T, j) = symb(Zji)... symb(Zjk)±,

где p(nji) = +Zji для 1 < i < k.

Заметим, что если m - максимальный из возможных для данного успешного маршрута T уровней, то для любой дуги уровня m ее заряд +Z удовлетворяет условию symb(Z) е Е U {±}. Более того, верна

Лемма 15. Если form(T,j) не содержит нетерминальных символов, то

form(T,j) = u(T)

□

Лемма 16. Пусть успешный маршрут T преобразователя M(G) имеет (T,j)-форму для некоторого j > 1. Тогда она является сентенциальной формой (вообще говоря, неправовыводимой) грамматики Augm(G). Следовательно, tu(T) е L(Augm(G)).

Доказательство. Достаточно доказать, что (T,j)форма является (D,j)кроной некоторого дерева D вывода в грамматике Augm(G).

Применим индукцию по номеру уровня. Для любого успешного маршрута T (T, 1)форма есть ±S±, т. е. (D, 1)крона любого дерева D вывода из начального символа So грамматики Augm(G). Пусть j > 1. Предположим, что )форма является (D,кроной для всех 1 < i < j. Теперь заметим, что (T,j)форма получается из (T,j - 1)формы заменой каждого нетерминального символа, отвечающего некоторой дуге уровня j - 1, правой частью правила, номер которого эта дуга пишет на выходную ленту (ср. лемму 14). Но тогда из предположения индукции следует, что (T,j)форма является (D, j)кроной, где деревья D и D совпадают до (j - 1)го уровня. Из доказанного и леммы 15 действительно следует, что пометка успешного маршрута принадлежит языку L(Augm(G)) □

Будем говорить, что преобразователь M допускает входную цепочку, если она допускается магазинным автоматом, согласованным с этим преобразователем. Множество всех допускаемых цепочек обозначим через L(M).

Теорема 6. L(M(G)) = L(Augm(G)). Для любой цепочки x G L(Augm(G)) множество

{П (Zo,x,Zo, А) Ь* (f, A,Zo, П)}

содержит все обращения правых выводов цепочки x.

Доказательство. Из леммы 13 следует, что M(G) допускает каждую цепочку из L(Augm(G)). Лемма 16 означает, что допускаются только они. Из указанного в доказательстве леммы 16 закона перехода от (T, j - 1) формы к (T, j) форме следует вторая часть теоремы □

2.2.2. Уменьшение степени недетерминированности преобразователя

M(G). Далее вместо пары команд (5), (6) будем рассматривать одну:

(9)(q, b, ZZ(1) ... Z(np)) - (a, p, ZZ1).

Так измененный преобразователь попрежнему называем M(G). Теперь преобразуем M(G) так, чтобы недетерминированность в его поведении уменьшилась. Обозначим новый преобразователь через ELRM(G). Его команда будет определяться некоторым множеством команд преобразователя M(G). Состояниями (и магазинными символами) станут некоторые объединения прогнозов, являющихся состояниями и магазинными символами преобразователя M(G). Начальное и заключительное состояния и маркер дна магазина наследуются от M(G).

Пусть v - прогноз. Пусть п = [pi,ji,ai] G v, i = 1,2. Пусть выполняется какое либо из следующих условий:

1)ji = nPl, J2 = nP2 и pi = p2, ai = a2,

2)j1 = npi, j2 < ПР2 и

Зж G (V U {-L})* : Xp2(j2+1) . . . XP2nP2 a2 =Augm(G) a1X.

Тогда будем говорить, что п1 и п2 конфликтуют (друг с другом) в v.

Обозначим через NoConfl(v) совокупность Set подмножеств прогноза v, получаемую действиями:

Set := {v},

пока Set содержит множество v, элементы п1 и п2 которого в нем конфликту -ют, выполнять присваивание

Set := Set - {v} U {v - {тп}, v - {n}}.

Так как любой шаг приведенного построения уменьшает мощности множеств, содержащих конфликтующие элементы, то для любого прогноза v (он конечен в силу конечности грамматики) множество NoConfl(v) существует и его мощность не превосходит v .

Теперь приведем формулы, которые позволяют построить все состояния, мага зинные символы и команды преобразователя ELRM(G), располагая только его начальным состоянием Z0 и командами преобразователя M(G).

Пусть 0 < p < s, пусть v и v(j), 0 < j < np, - состояния (и магазинные символы) преобразователя ELRM(G), a G £ U{±}. Введем обозначения:

vert(v, a) = NoConfl({r G Z (q, b, Z) - (ZЛ, ZZ) G 5m(g),

Z С v, (q,b) G{(Z,a), (a, Л)}})

vert(v(0),... ,v(np),p, a) = NoConfl({r G Z (q, b, Z(0)Z(1)... Z(np)) - (a,p, Z(0)Z) G 5m(g); для 0 < j < np Z(j) С vj; (q,b) G {(Z(np),a), (a, Л)}}). Тогда ELRM(G) имеет команды:

(10)(q, b, v) - (v, Л, vv), v G vert(v, a), (q, b) G {(v, a), (a, Л)},

(11)(q,b,v(0)v(1) ...v(np)) - (a,p,v(0)v), p> 0,

v G vert(v(0),..., v(np),p, a), (q, b) G {(v(np), a), (a, Л)}.

(12)(±, Л,ZoV(1)v(2)) - (f, 0,Zo), [0,1, Л] G v(1), [0, 2, Л] G v(2).

Пример 2. Для грамматики G с правилами