так как граф рассматриваемого магазинного автомата не имеет кратных дуг с одинаковыми пометками. В записи маршрута будем однократно выписывать общую вершину двух последовательных дуг. Предварительно введем буквенные обозначения для элементов множества V(Z), так как это сделает запись дуги компактней: A = [(o,Zo], В = [(и, 0], C = [)ц, 0], D = [(i, 0], E = 0], F = [)o,Zo],

G = [(i2i, 1], H = [)i2i, 1), I = [(i22, 1], J = [)i22, 1], K = [(i, 122], L =122],

M = [(i22i, 122], N = [)i22i, 122], P = [(2i, 0], Q = [)2i, 0].

Если положить Ti = АЛРAQAD, T2 = АЛВACAD, T3 = DAEAF, T4 = GaHAIAKAG и T5 = JALAMbNAJ, то искомая формула есть

{Ti,T2}({T3} U {T4 GaHAIAKALAMbNAJ T JAEAFi > 0}).

3.3. Согласующие выражения. Пусть projection(w, E) G E+ для цикла w некоторой фракции над E. Тогда назовем цикл w помеченным.

Пусть £ = u(lx(ly)lz)lv есть фракция, в которой циклы (Lx и z)u оба являются помеченными. Тогда назовем фракцию £ вставляющей (подразумевается вставление цепочки именованного языка внутрь цепочки того же языка, наблюдающееся в результате образования фракций u((,x)m(ty)t(z)t)mv).

Пусть Z - КСвыражение. Если множество Clan(Z) содержит вставляющую фракцию, то назовем выражение ( согласующим, иначе псевдосогласующим.

Лемма 17. Если ( - согласующее выражение, то существует такая вставляющая фракция £ G Clan(Z), что height(£) < 5.

Доказательство. Пусть £ G Clan(Z) - вставляющая фракция. Согласно опре -делению вставляющей фракции имеем равенство

£ = u/(txiax2(ty/)tzi bz2 )tv

для некоторых имени i G Names(£), цепочек

u/>xi>x/2>y/>zi,z2,v G Alph(C)* и символов a, b G E. Пусть

£ = u(txiax2(ty)tzibz2 )tv) G reduction, (t,xi,a,x2, (i, y/, )i, zi ,b,z2, )t, v/),

S G {u,xi,x2,y,zi,z2,v}

обозначает образ цепочки s/ при данном редуцировании.

Заметим, что projection(£, B(()) является скобочной системой. Следовательно, если некоторый цикл содержит выделенную в записи фракции £ скобку (1 или )t, то парная ей скобка содержится либо в том же цикле, либо в парном ему цикле. Учитывая данное обстоятельство, докажем, что h(k,£) < 5 для любого имени k G Names(().

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

Рассматривая все допустимые варианты положения скобок (k и )k, k G Names((), во фракции £, нетрудно убедиться, что при k = i максимум числа

h(k, С) достигается в случаях, когда фракция С имеет одну из следующих двух форм:

Щ(к «2(1X11 (к Ж12ЙЖ21 (k X22(k X23(tyi(fe У2)кУъ)ь Zll )k Zi2&Z2l)fc 22) 23)1) V2, Ul(fc «2(1X11 (k X12(k X13«X21(k X22(iy1(k У2)кУз)ь Z11 )k Z12)k ZbZ21)k Z22)tVk V2,

а при k = i - в следующих двух случаях:

С = w(iXn(tX12aX2(ty)tZn)tZ12bZ2)t v, С = «(tX1aX21(tX22(ty)tZ16z21)tZ22)t V.

Итак, h(k, С) < 5 для k G Names((), т.е. height(C) < 5. Парные циклы (lX1aX2 и z1bz2)l являются помеченными, так как projection((lX1aX2, £) и projection(z1bz2)l, Е) содержат символы a и b соответственно. Следовательно, фракция С является вставляющей □

Лемма 18. КСвыражение ( является псевдосогласующим тогда и только тогда, когда каждая фракция любого элемента из Core((, 5) не является вставляющей.

Доказательство. Необходимость ясна из определений. Для доказательства достаточности заметим, что противное не совместимо с леммой 17 □

Теорема 9. Если ( - псевдосогласующее КСвыражение, то язык Ь(() регулярен.

Доказательство. Граф Л(() с множеством вершин V(() и множеством дуг E(() представляет конечный автомат, эквивалентный псевдосогласующему выражению Z (если, как и для графа D((), вершины [(0,Z0] и [)0, Z0] считаются входной и заключительной соответственно).

Действительно, если - псевдосогласующее КС выражение, то для определе ния языка L(Z) можно вместо Clan(Z) использовать Paths(():

так как требование баланса парных циклов избыточно в данном случае. Заметим, что множества Paths(Z) и Paths(Augm(()) определяют один и тот же язык, а

Paths(Augm(()) = DisBal((0, )0).

По следствию 1 существует такая биекция

у : T([(0, Z0], [)0, Z0]) -> DisBal((0, )0),

что для каждого пути T G T([(0, Z0], [)0, Z0]) выполняется равенство

4>(T)state(end(T)) = у(Т).

Последнее соотношение влечет равенство

и(<р(Т)) = {и(Т)}.

Но множество T([(0,Z0], [)0,Z0]) есть множество успешных путей автомата Л((). Следовательно,

L(Z) = {и(Т)\Т G T([(0, Z0], [)0, Z0])} = L(A(Z))

□

3.4. Об укорачивании КСвыражений. Начнем с примера, объясняющего идею укорачивания.

Пример 14. КСвыражение

Z = a(ia(i6)ib)ib(ia(i6)ib)i

задает язык

{a}{anbn\n > 0}{b}{anbn\n > 0} = {ambmanbn\m > l,n > 0}.

Из определений КСвыражения и задаваемого им языка следует, что КС-выражения

a(ie)ib(ia(i6)ib)i

a(ia(ie)ib)ib(i6)i

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

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

КСвыражение 0 не нуждается в укорачивании. Рассмотрим поэтому случай КСвыражения (, для которого

Trim(Z) = 0.

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

Е «•

так как может содержать несколько экземпляров своей приведенной фракции. (Эта неэкономность также будет преодолеваться.)

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

Объявленный алгоритм можно интерпретировать как алгоритм укорачивания множества приведенных фракций произвольного КСвыражения. Важное приложение алгоритма состоит в том, что он указывает способ укорачивания ядра и характеристики бесконтекстной грамматики (см. п.2.2.1).

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

ATnm(() = {(о£)о£ е Tnm(()},