Если rlf (T) = T1, n2, T2), то (1,1)ядро Эграфа содержит маршрут с право-линейным разложением (n1,T1/,п2,Т2), где pair(T{) = pair(T) для i = 1, 2. (Действительно (ср. лемму 6), таков каждый маршрут из reduction(n1,T1,n2,T2) С Core(D, 1,1).) Как будет ясно из дальнейшего, это означает, что (1,1)ядро D-графа содержит всю необходимую информацию для осуществления предлагаемых ниже построений. Далее пишем Core(D) вместо Core(D, 1,1).

Назовем фразой Dграфа D элемент следующего рекурсивно определяемого множества нейтральных маршрутов: Phrases(D) = Sentences(D) U {T1, T23((7ri,7T2) e V, T e Phrases(D)) (m,,72) = rlf (T)}.

Построим по Dграфу D КСвыражение E(D) над алфавитом дуг E(D). Для индексации скобок, составляющих алфавит B(E(D)), используем элементы мно -жества

{pair(T)T e Phrases(D)}.

В следующих множествах фраз каждый элемент, который является пустым маршрутом, следует считать синонимом обозначения Л, а сами множества - языками в алфавите E(D):

Alt(P,Q) = {T e Phrases(D)lpair(T) = (P,Q)},

Productions(P, Q) = Alt(P, Q) П Core(D).

Пусть T e Phrases(D). Тогда схема scheme(T) фразы T определяется рекур -сивно следующим образом:

1)если фраза T пуста, то scheme(T) = (pair(T))Pair(T);

2)если rlf(T) = (m,T1,n2,T2), то

scheme(T) = (pair(T)n1scheme(T1)n2scheme(T2))pair{T).

Ясно, что схема удовлетворяет определению фракции над алфавитом E(D). Будем считать, что пометкой фракции (pair(T))pair(T) является {T}. Хотя пустых фраз может быть много, нужный синоним обозначения Л однозначно устанав ливается по индексу pair(T) скобок данной фракции. Действительно, вершина beg(T) = end(T) и является представлением пустого маршрута T. Это соглашение о пометке удобно в доказательстве нижеследующей леммы 3.

Конструкция выражения E(D) очень проста:

E(D) =scheme(T).

Q&F T&Productions(Po,Q)

Из определения фразы следует, что Alt(P, Q) есть множество {n1T1n2T2beg(n1) = P; parti (K1T17y2) = 1; T e Alt(end(n1),beg(n2)); T2 e Alt(end(n2), Q)}, объединенное с {P} при P = Q.

т(P, Q) = {scheme(T)T e Productions(P, Q)}. Обозначим через Lpqq язык, задаваемый суммой У6г(pq) £. Ясно, что

Lp,q С Alt(P,Q).

Докажем, что

Alt(P,Q) С Lpq. Для этого докажем следующую лемму.

Лемма 12. Пусть T - фраза. Тогда T е Lpair(T). Доказательство. Пусть

с = £ £

£€т (pair(T))

Заметим, что из построения схем следуют равенства

Fractions(C) = Trim (С) = т (pair(T)).

Вследствие теоремы 7 достаточно доказать, что T е ш(ф), где (С, Ф)для

некоторых £ е т(pair(T)) и m > 0. Применим индукцию по k > 0, где 2k - длина фразы T.

При k = 0 фраза T пуста. Следовательно,

С = (pair(T)6)pair(T) е т(pair(T)).

Так как (С, С) е0 и T е утверждение в данном случае верно.

Пусть k > 0. Предположим, что утверждение справедливо для всех фраз, длина которых меньше, чем 2k, и рассмотрим фразу T длины 2k. Допустим, что

rlf (T ) = (n1,T1,n2,T2).

Из предположения индукции следует, что для i = 1, 2 верно соотношение Ti е ш(фг), где (Сг,фг)для некоторых £ е т(pair(T)) и mi > 0. Можно считать

(ср. соотношение для Со в теореме 7), что height(Ci) = 1, i = 1, 2. Но тогда

С = П1С1П2£2 е т(pair(T)).

Так как

(СП1Ф1П2Ф2) е1+т2

T = П1 Ti2T2 е (101202),

утверждение верно и при k > 0. Итак, T е Lpair(T) □

Из леммы следует равенство L(E(D)) = Sentences(D).

Заметим, что L(D) есть совокупность пометок всех маршрутов, которые входят в Sentences (D).

Определим морфизм </? соотношениями:

у?(п) = о>(п), п е E(D); </?(a) = a, a е E(D).

Тогда ясно, что КСвыражение Expr(D) = ip(£(D)) задает язык L(D). Это означает, что любой бесконтекстный язык определяется некоторым КСвыражением.

Пример 12. Пусть D есть граф магазинного автомата M, рассмотренного в примере 6. Вместо выражения Expr(D), страдающего избыточностью, приведем несколько менее избыточное эквивалентное выражение С, построенное по следующим двум элементам множества Productions((p0, Z0), (f, Z0)): 157898, 12234678.

Пары концов фраз, входящих в эти успешные маршруты, дают семь имен: 1)

((pb Zо), (f, Z0)), 2) ((p0,a), (p0,a)), 3)(f, Z0)), 4) ((p2,a), (p2,a)),

5) ((f, Z0), (f, Z0)), 6) ((p0,a), (p1,a)), 7) ((p1,a), (p1,a)). В выражении С будем писать вместо перечисленных имен их порядковые номера:

С = ((26)26(3(4 6)4(5(46)4(56)5)5)3)1+

(ia(6a(6 0(26)26(76)7)66(76)7)66(3 (46)4(56)5)3)1-Символы a, b, перемежающие собой именованные скобки, отвечают пометкам дуг; 6 отвечает пустому участку.

Теперь докажем, что каждое КСвыражение определяет некоторый бесконтекстный язык. Достаточно рассмотреть случай, когда клан КСвыражения непуст; в противном случае выражение задает пустой язык, относящийся к бесконтекстным.

Сначала преобразуем КСвыражение (пусть это Z) к виду, удобному для построения эквивалентного выражению магазинного автомата. В нашем построении важна роль гнезд; им соответствуют четко обособленные подавтоматы. Добьемся некоторой стандартной организации гнезд, входящих в элементы клана, вводя, если нужно, дополнительные имена. Можно заранее рассчитывать, что любая фракция в клане является произведением не менее чем двух сомножителей, а для каждого гнезда (1в)1, которое входит в некоторую фракцию из Clan((), либо в Е X U {6}, либо в является произведением по крайней мере двух сомножителей. Действительно, для выполнения этих требований достаточно добавить сомножи тели 6 к каждой фракции из Fractions(Z), а каждое входящее в такую фракцию гнездо вида

где в Е Alph(Z)+, i1, i2 Е Names((), заменить на

Пусть КСвыражение либо является именованным, либо совпадает с некоторым a Е X U {6, 0}. Тогда назовем это выражение неделимым.

Определяемая непосредственно далее разметка фактически ранжирует недели -мые сомножители внутри отдельных гнезд и во фракциях в целом. Вводимая разметкой упорядоченность сомножителей позволяет отвлечься от ассоциативно сти умножения и вследствие этого уменьшить размеры автомата, производимого по КСвыражению. Но главное назначение разметки - решить проблему различения вхождений одних и тех же участков в рассматриваемые фракции. Так, для любой фракции xay Е Clan(Augm(()), где a Е X U {6}, а Augm(Z) опре -деляется (см. ниже) по КСвыражению ( над алфавитом X с помощью разметки, цепочка projection(x, B(Augm(())) уникальна, т.е. может использоваться для идентификации рассматриваемого вхождения a. Эта особенность весьма облегчает доказательство корректности нашего построения магазинного автомата по КС выражению.

Пусть £ = 0 приведенная фракция, к - конечная последовательность некоторых натуральных чисел. Назовем разметкой фракции £ (с помощью к) и обозначим через rlm(£, к) следующую рекурсивно определяемую фракцию:

1) если a Е X U {6}, то

rlm(a, к) = (Ka)K

rlm((La)i, к) = (ta)i

для любого имени i;