цепочка

projection(Z, B)

является скобочной системой.

Пусть ь Е Names Тогда назовем ь-высотой КСвыражения ( число

h(i, () = depth(projection((, {(t, )t})).

Здесь depth(x) обозначает глубину скобочной системы x, определенную в параграфе 1.

Назовем высотой КСвыражения ( число

height(Z) = max{h(i,()ь Е Names(()}.

Подцепочки (x и z)t КСвыражения

u(lx(ly)lz)lv

назовем его парными друг другу циклами (или, если информация об имени существенна, 1-циклами), левым и правым соответственно.

Заметим, что если (x и z)t - парные циклы некоторой фракции и u - ьгнездо в ней, возможно, даже не содержащее этих циклов, то (ixuz)i является ьгнездом в некотором элементе клана. Этим оправдывается целесообразность определяемого далее отношения развития.

Пусть d > 0. Назовем d-ядром КСвыражения ( и обозначим через Core((, d) подмножество всех элементов его клана, высота которых не превосходит d:

Core((,d) = {С Е Clan(()lheight(£) < d}.

Покажем конечность множества Core((,d).

Из определений фракции и клана следует, что для любой фракции С Е Clan(() выполняется неравенство

width(projection(C, B(Z))) < width(projection(Z, B(())),

где width(x) обозначает ширину (см. определение в параграфе 1) скобочной си -стемы x. Кроме того, каждое подвыражение ф Е (Т, U {е})* такой фракции не длиннее выражения (, т.е. между последовательными вхождениями скобок во фракцию расположена цепочка, длина которой ограничена длиной исходного КС выражения. Из определения высоты КС выражения следует, что для любой фрак ции С Е Clan(() глубина

depth(projection(C, B(Z)))

не превосходит произведения d-lNames(()l. Значит, множество Core((,d) конечно вследствие теоремы 1 (она же есть теорема 1 работы [Станевичене 99]).

Пусть ьгнездо u входит в некоторый элемент клана КСвыражения ( и удовлетворяет условиям h(i, u) = 2, h(o, u) < 2 для любого имени o = ь. Тогда назовем u формантом выражения (.

Лемма 10 (см. ниже) показывает, что все форманты КСвыражения обнаруживаются в элементах его 2ядра.

Определим на множестве Clan(Z) отношение непосредственного развития ffz: пусть u = v(1x(1y)1z)1w G Clan(Z), где (1x(1y)1z)1 является формантом. Тогда

«y)tw,u) efc.

Пятерку

будем называть историей непосредственного развития выражения u из v(1y)1w. Отношение назовем отношением развития.

Уподобляя циклы КСвыражения таковым Dграфа, нетрудно определить аналог функции reduction, отображающий разложение КСвыражения в множество КСвыражений и вычеркивающий в исходном выражении циклы, которые можно вычеркнуть, не затрагивая некоторых выделенных участков выражения. Этой новой функции также дадим имя reduction.

Более аккуратно, пусть k > 1, а ( = x\.. .xk - КСвыражение, части Xj которого могут и не быть выражениями. Обозначим через reduction(x\,..xk) мно -жество всех КСвыражений, получаемых из ( такими удалениями (они делаются, пока возможны) парных циклов, что части x2i, 2 < 2i < k, не затрагиваются.

Лемма 10. Если a[3j G Clan((), а в является формантом, то reduction(a, в, Y) С Core((, 2).

Доказательство. Пусть

oi eY G reduction(a, e,Y),

где o и Y являются образами цепочек а и y при данном редуцировании. Предпо -ложим, что для некоторого имени i выражение oOeY содержит гнездо £ высоты 3. Заметим, что границами гнезда являются парные друг другу скобки. Следо -вательно, если гнезда u и v суть различные участки одного КС выражения, то либо они не имеют общего участка, либо одно из гнезд является участком дру гого. Отсюда получаем, что гнездо £ содержит в себе формант в, так как внутри форманта не может быть гнезда столь большой высоты, а наличие гнезда £ вне в противоречит построению выражения oOeY. Но тогда, опятьтаки вследствие определения форманта, oO и Y должны соответственно содержать левый и правый циклы гнезда £, что противоречит построению выражения oOП

Лемма 11. Если фракция £ G Clan(() содержит циклы, то существует такая фракция £ G Clan((), что (£,£) Gfc и £ < £.

Доказательство. Докажем, что £ содержит формант. Среди ее гнезд, принадле -жащих множеству Nests = {u\z\(v,w G Alph(()*, i G Names(()) (£ = vuw, u - бгнездо, h(i,u) > 2)}, выберем выражение с наименьшей длиной. В силу выбора оно не содержит собственных подвыражений, принадлежащих множеству Nests, т.е. является формантом. Пусть £ = aвY, где в = (1x(1y)1z)1 - выбранный фор -мант. Тогда согласно определению отношения непосредственного развития для £ = o(iy)iY имеем (£,£) Gfc и £ < £ П

Теорема 7. Пусть ( есть КСвыражение. Для любого выражения £ G Clan(() существуют такие число k > 0 и последовательность КСвыражений £0,...,£k, что £0 G Core((, 1), £k = £ и (£i-i,£i) Gfz для 0 < i < k с некоторой историей

непосредственного развития (uxy, zy), причем формантсодержится в

некотором элементе ядра Core(Z, 2).

Доказательство. Для £ е Core(Z, 1) теорема верна при k = 0. Пусть теперь £ е Clan(() - Core(Z, 1). Тогда £ содержит циклы. По лемме 11 существует такое выражение £ е Clan((), что (£,£) и £ < £. Из последнего неравенства следует, что существуют k > 1 и последовательность £0,---,£k, такие, что £0 не содержит циклов (т.е. входит в Core(Z, 1)), £k = £ идля 0 < i < k

с некоторой историей непосредственного развития (ui,Xi,yi,Zi,Vi). По лемме 10 формант XiyiZi содержится в некотором элементе ядра Core(Z, 2) □

Пример 11. Язык

{a}U{ambnm > 1,n > m} может быть задан КСвыражением

Z = a + (ia(i ab)i 6)1(2(26)2)2-Наибольшие два из четырех его гнезд являются формантами.

Clan(Z) = {a} U{[(ia]k(iab)i[b)i]k[(2(26)2[b)2]k, l > 0}.

Простейшими элементами этого клана являются не содержащие циклов фракции a и (iab)i(2e)2. Объединение их пометок {a, ab} содержит две самые короткие цепочки языка Ь((). Для любого целого d > 1

Core((,d) = {a} U {[(ia]k(iab)i[b)i]k[(2]1 (26)2[b)2]0 < k, l < d}.

3.2. Эквивалентность КСвыражений и Эграфов. Следующий прием перевода регулярных выражений в КС выражения специального вида показывает, что последние можно считать формой записи регулярных выражений и что приведен ная далее теорема 8 - достаточно естественное обобщение теоремы Клини.

Пусть a - регулярное выражение над алфавитом Е. Тогда L(a) = L(a(a)), где КСвыражение a(a) определяется рекурсивно следующим образом:

1)a(a) = a, a е Е U {е, 0};

2)если в и 7 - регулярные выражения, то <т(в + 7) = а(в) + с(т), )(т)) = (а(в))(а(7)) и *((£)*) = (ва(в)(ве)в)в.

Теорема 8. Язык задается КСвыражением тогда и только тогда, когда он определяется некоторым D графом.

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

Для D графа используем наше обычное обозначение

D = (Е, V, P, Л, Po, F)-

Назовем праволинейным разложением непустого нейтрального маршрута T чет -верку

где (ni,n2) е P, parti(niTi) = 1, T = пя.

Праволинейное разложение маршрута определяется однозначно, так как у маршрута не может быть двух начальных участков протяжения 1.