V(Z) := V(Z) U {PP - вершина какойлибо из дуг, участвующих в элементах множества NewP}.

Dграф, полученный в результате данного построения, обозначим через D(Z). Для s > 0 и P, Q е V(Z) введем обозначение T(P, Q, s) для всех путей этого графа (они могут и не быть маршрутами) длины s с парой концов (P, Q). Пусть

T (P,Q) = Us>qT (P,Q,s).

Назовем путем КСвыражения Z элемент следующего рекурсивно определяемого множества Paths(Z):

Paths(Z) = Clan(Z) U {x[(u]k(ty)t[v)Alzx(tu(iy)iv)iz е Paths(Z), k, l > 0}.

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

Для s > 0 и b1,b2 е B(Augm(Z)) введем обозначение DisBal(bi,b2, s) для следующего множества непустых участков путей из Paths(Augm(Z)):

DisBal(b1,b2 ,s) = {b1yb2\s = lprojection(b1yb2, B(Augm(Z)))l - 1}.

Здесь значение s аналогично длине пути на графе, измеряемой в дугах. Пусть

DisBal(b1, b2) = Us>0DisBal(b1, b2, s).

Для вершины P = (p, Z) обозначим состояние p через state(P). Определим морфизм

Ф : E(()* - ({state(beg(n))ln е E((Ш U {A}))*,

полагая

Ф(п) = state(beg(n))uj(n). Здесь значение s аналогично длине пути на графе, измеряемому в дугах.

Лемма 16. Для любых s > 0 и P,Q е V(Z), если T(P, Q, s) = 0, то существует такая биекция

ц> : T(P, Q, s) - DisBal(state(P), state(Q), s), что для каждого пути T е T(P, Q, s) выполняется равенство

Ф(T)state(end(T)) = y(T).

Доказательство. Докажем лемму индукцией по s. Рассмотрим случай s = 0.

T(P, Q, 0) = {P} при P = Q и пусто при P = Q. При state(P) = state(Q)

имеем DisBal(state(P), state(Q), 0) = {state(P)}, при state(P) = state(Q) DisBal(state(P), state(Q), s) пусто. Следовательно, в данном случае лемма верна.

Пусть s > 0. Предположим, что для любых 0 < s < s и P,Q е V(Z), удовле -творяющих неравенству T(P, Q, s) = 0, существует такая биекция

Ч> : T(PQ, s) - DisBal(state(P), state(Q), s),

что для каждого пути T е T(P, Q, s) выполняется равенство

Ф(T)state(end(T)) = <p(T).

Пусть T(P, Q, s) = 0. Тогда из построения множеств E(Z) и V(Z) следует воз -можность ровно двух случаев: P = [(m, Z] для некоторых m е Names(Augm(Z))

и Z £ Names(Augm(Z)) U {Z0} или P = [)k, m] для некоторых k, m £ Names(Augm(()). Каждая из вершин

[(m,Z],,m]

может быть начальной вершиной дуг двух видов. Следовательно, T(P,Q,s) совпадает с одним из следующих двух объединений:

{[(m,Z]A[(k,m]TP = [(m,Z]; (3l £ N ames(Augm(Z)) (k,l,m) есть альянс); T £ T([(fe,m],Q,s - 1)} U {[(m, Z]a[)m, Z]TIP = [(m, Z]; a £ E; (ma)m есть активное гнездо; T £ T([)m, Z], Q, s-l)}U {[(m, Z]A[)m, Z]TIP = [(m, Z]; (mt)m есть активное гнездо; T £ T([)m,Z],Q,s - 1)};

{[)k,m]A[(i,m]TIP = [)k,m]; (k,l,m) есть альянс; T £ T([(t,m],Q,s - 1)} U {[)k,m]A[)m, Z]TIP = [)k,m]; (3l £ Names(Augm(Z)) (l,k,m) есть альянс); T £ T([)m,Z],Q,s - 1)}.

Цепочка из множества DisBal(h\,b2, s) начинается скобкой Ъ\ и заканчивается скобкой Ъ2. Скобка Ъ\ может быть как открывающей, так и закрывающей. Согласно структуре фракций выражения Augm(Z) в пути из Paths(Augm(()) за открывающей скобкой идет либо открывающая скобка, либо символ a £ E U {е}, а закрывающая скобка, отличная от )0, всегда предшествует скобке, открываю щей или закрывающей. Более того, указанные двухсимвольные участки путей из Paths(Augm(Z)) несут информацию об активных гнездах и альянсах, которую мы выразим в двух нижеследующих формулах, характеризующих значение множества DisBal(state(P), state(Q), s) при state(P) = (m и state(P) =)k соответственно. Здесь k,m £ Names(Augm(Z)).

{(m(kyIstate(P) = (m; 3l £ Names(Augm(Z)) (k,l,m) есть альянс; (ky £ DisBal((k, state(Q),s - 1)}U {(a) my I state (P) = (m; a £ E U {е}; (ma)m есть активное гнездо; )my £ DisBal()m, state(Q), s - 1)}.

{)k(lyIstate(P) =)k; 3m £ Names(Augm(Z)) (k,l,m) есть альянс; (iy £ DisBal((l, state(Q),s - 1)}U {)k)myIstate(P) =)k; 3l £ Names(Augm(Z)) (l,k,m) есть альянс; )my £ DisBal()m, state(Q), s - 1)}.

Сопоставляя последние формулы с формулами для T(P, Q, s), выводим, что из существования биекции у следует, что отображение </?, определяемое соотношениями

y(nT) = $>(n)y(T), nT £T(P, Q, s),

есть требуемая биекция □ Очевидно

Следствие 2. Для любых P,Q £ V((), если T(P,Q) = 0, то существует такая биекция

у : T(P, Q) DisBal(state(P),state(Q)), что для каждого пути T £ T(P, Q) выполняется равенство

(T)state(end(T)) = y(T)

□

Следствие 3. L(D(()) = L(().

Доказательство. По следствию 2 существует такая биекция у : Sentences(D(Z)) - Clan(Augm(Z)),

что для каждого предложения T выполняется равенство

<&(T)state(end(T)) = t/?(T).

Следовательно,

lo(T) = projection(cp(T), X).

Значит,

L(D(Z)) = L(Augm(()).

Но КСвыражения Augm(() и ( эквивалентны □

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

Пример 13. КСвыражение ( = (la(ie)ib)1 задает язык [anbn\n > 0}. Core(Z, 2) содержит два элемента: ( иMark(() содержит

(0(1ie)11(1 (121a) 121 (122(l£)1(1221b) 1221 )122)1)0 и (0(2121 (1е)1)0.

Names(Augm(()) = {0,1,11, 21,121,122,1221}.

Активные гнезда представляют четыре альянса:

(11,1, 0), (121,122,1), (1,1221,122) (21,1, 0).

Предоставляем читателю вычислить множество Core(Augm((), 3) и убедиться, что других альянсов для данного примера не существует. Автомат M(() есть семерка

(K, {a,b}, {Z0} U Names(Augm(Z5С, (0, О0}),

где Kz = {(m, )m\m E Names(Augm(())}, а 5z определяется следующими командами:

((0, A,Z0) - (d,Z00);

((i, A, 0) - ()t, 0) и ()t, A, 0) - ((1, 0), где i E {11, 21};

((1, A, Z) - ()1 ,Z) и ((1, A, Z) - ((121, Z1), где Z E {0,122};

((121, a, 1) - ()121, 1);

0121,A, 1) - ((122,1); ((122, A, 1) - ((1,1 122);

A, 122) - ((1221,122); ((1221, b, 122) - O1221,122); O1221, A, 122) - O122, A);

0122,A, 1) - A); A, 0) - ()0, A).

Составим формулу для множества успешных маршрутов построенного автома -та. В данном примере можно отождествить дугу с некоторой тройкой из

V(() х (X U{A}) х V((),