2) если а является неделимым КСвыражением, то

rlm(a(, к) = (кrlm(a, (к, 1))rlm((, (к, 2)))к,

rlm((ua()u, к) = drlm(a, (к, 1))rlm((, (к, 2)))t

для любых фракции ( и имени i.

Как видим, любые две пары скобок, добавленные разметкой, индексируются различными именами.

Пусть клан КСвыражения ( непуст; пусть цифра 0 и кортежи натуральных чисел не используются в ( как имена гнезд. Занумеруем элементы множества Core((, 2) в некотором порядке и обозначим через v(£) номер фракции £ е Core((, 2). С помощью размеченных фракций 2ядра определим множество Mark(Z) следующим образом:

Mark(() = {rlm((o£)о, vе Core((, 2)}.

Назовем пополнением КСвыражения ( сумму фракций, составляющих множество

Mark(():

Augm(z) =£.

Следующая лемма используется в доказательстве эквивалентности выражений

и Augm( ).

Лемма 13. Пусть клан КСвыражения ( непуст. Тогда:

1)Core(Z, 1) = {projection(£, Alph(())\£ е Core(Augm(Z), 1)};

2)множество формантов КС выражения совпадает с

{projection(£, Alph(())\£ - формант выражения Augm(()}.

Доказательство. Заметим, что к,ф) < 1 для ф е Mark(() и любого имени к, введенного разметкой, которая превращает множество Core((, 2) в Mark((), т.е. для к е Names(Augm(()) - Names(Z). Следовательно, каждый формант, участвующий в некоторой фракции из Core( , 2), превращается в формант ее разметки. Других формантов фракции из Mark(() не содержат.

Отсюда ясно, что Core(Augm((), 1) совпадает с

{£ е Mark(Z)\projection(£, Alph(Z)) е Core(Z, 1)}.

Так как

Core((, 1) С Core(Z, 2) = {projection, Alph((е Mark(()},

первое из утверждений леммы справедливо.

Из последнего равенства вытекает совпадение множества формантов выраже -ния с множеством

FS = {projection(£, Alph((- формант,

3(u,v е Alph(Augm(Z))*) u£v е Mark(()}.

Вообще говоря, фракции из Mark(Z) содержат не все форманты выражения Augm((). В самом деле, если в них есть одноименные форманты

где x1y1z1 = x2y2z2, то в элементах клана Clan(Augm(()) присутствуют форманты

(1X1 (ty2)tZi)t и (t2(tyi)tZ2)t.

Однако по лемме 11 проекции всех четырех рассмотренных формантов на Alph(() присутствуют в элементах 2ядра выражения (. Таким образом, множество FS содержит проекции на Alph(() всех формантов выражения Augm((), одноименных с формантами выражения (. Следовательно, для доказательства второго из утверждений леммы теперь достаточно убедиться, что выражение Augm(() не имеет формантов с именами из N ames(Augm(()) - Names(().

Если к Е Names(Augm(()) - Names((), то любое кгнездо кглубины 2 не является формантом. Действительно, вследствие уникальности каждой пары скобок, поставленной при разметке, гнездо v вида (Kx(Ky)Kz)K может появиться в элемен -те множества Clan(Augm(()) - Mark(() только в результате последовательного использования для развития фракций из Mark(() некоторых формантов

(1 ui (2(3)4)5)1, (1(2(3)4)5)1

с одними и теми же парными циклами. Следовательно, глубина гнезда v не меньше двух, и оно не удовлетворяет определению форманта.

Таким образом, элементы из Names(Augm( )) - Names( ) играют роль ин дивидуальных имен подвыражений фракций из Core((, 2); на образование клана выражения Augm( ) влияют только гнезда с именами из Names( ), отличаю щиеся от гнезд множества Core((, 2) лишь присутствием "индивидуализирующих скобок". Следовательно, верно и второе из утверждений леммы □

Лемма 14. Выражения ( и Augm(() эквивалентны.

Доказательство. Достаточно доказать, что клан Clan(Augm(()) сюръективно отображается на Clan(() и образом фракции £ Е Clan(Augm(()) является

projection, Alph(()) Е Clan(().

Но этот факт вытекает непосредственно из нижеследующего утверждения, ко -торое легко доказать индукцией по k, опираясь на установленные в лемме 13 взаимосвязи ядер и формантов выражений и Augm( ). Пусть k > 0. Тогда

{projection(£,Alph(())\3£о Е Core(Augm((), 1) (Со,С) EfkAugm{0} = [ф\Зфо Е Core((, 1) (фо,ф) }

□

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

Будем называть активным гнездом любое именованное выражение, входящее в некоторую фракцию из Clan(Augm( )).

Пусть k,l,m Е Names(Augm(Z)), а, в Е Alph(Augm(())* и С = (m(ka)k(1 в)i)m - активное гнездо. Тогда назовем тройку (k, l, m) альянсом и будем говорить, что С представляет этот альянс.

Заметим, что по построению разметки каждое активное гнездо либо представ -ляет некоторый альянс, либо имеет вид

(1a)1, a Е X U {е}, i Е Names(Augm(()).

Лемма 15. Пусть (m(ka)k(i()i)m - активное гнездо. Тогда существует активное гнездо (m(ka)k(l)m, которое входит в некоторую фракцию из Core(Augm(Z), 3).

Доказательство. Согласно определению активного гнезда существуют такие u,

v Е Alph(Augm(())*, что

u(m(ka)k(i()i)mv Е Clan(Augm(Z)).

kВысота фракции

£ Е reduction(u, (m(k,a)k, (i,()i)mv) может достигать трех. Действительно, пусть £ имеет вид

ui (k u2(m(k ai (k a2)k a3)k (i( )i )mVi)k v2.

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

Нетрудно убедиться, что для любых других допустимых случаев положения скобок (k и )k неравенство h(k,£) > 3 не выполняется. Аналогично, h(l,£) < 3. Для любого другого имени i Е Names(Augm(Z)) h(i,£) < 2 □

Лемма 15 означает, что любой альянс представлен некоторым гнездом, входя -щим в выражение из Core(Augm((), 3). Это оправдывает следующее использова -ние множества Core(Augm((), 3) для построения эквивалентного КСвыражению Z магазинного автомата

M(Z) = (B(Augm(()), Т,, Names(Augm(()) U [Z0], Z0, 5((), (0, {)0}).

Так как доказательство эквивалентности выражений Augm(() и M(() удобно вести в терминах маршрутов, построим вместо 5(() Dмножество P(() автомата M((), разрешая в качестве его элементов нейтральные дуги. Нейтральную дугу здесь следует рассматривать как сокращающее представление пары дуг, которые могут образовать гнездо только с пустым серединным элементом. Естественно также считать нейтральную дугу элементом множества P((). Зная Dмножество P((), легко построить команды автомата:

5(() = {(p1,a1,Z) (q1,ZX), (p2,a2,Z) (Q2, Л)\

((pi ,Z )ai(qi,X), (p2,X )a2(Q2,Z)) ЕР (()}U

{(p,a,Z) - (q, Z)\(p, Z)a(q, Z) ЕР(()}.

Сформулируем алгоритм постепенного построения множества Р((), начинаю -щий с образования дуг, инцидентных входной или заключительной вершине. Для ссылки на множества построенных дуг и их вершин будем употреблять обозна чения E(Z) и V(() соответственно:

Р(Z) := 0;

V(() := {[(o,Zo], [)о,Zo]}.

Пока следующие три присваивания влекут добавление в V( ) новых элементов, повторять их:

NewP := {([(m,Z]k[(k,m], [)i,m]A[)m, Z]), [)k,m]A[(i,m] \[(m, Z] Е V((); (k,l,m) есть альянс } U{[(m, Z]a[)m, Z]\[(m, Z] Е V((); a Е Т; (ma)m есть активное гнездо } U{[(m, Z]A[)m, Z]\[(m, Z] Е V((); (mt)m есть активное гнездо };

P(Z) := P(Z) U NewP;