не являются вставляющими. Допустим, что фракция

£т = y>(scheme(T))

является вставляющей. Тогда в scheme(T) есть парные ршг(Т)циклы, пометки которых (напомним, что это маршруты) обе несут цепочки из Е+. Следовательно, левый из этих циклов не есть моном в Т, вопреки праволинейности автомата M. Сообразуясь с замечанием, сделанным выше, выводим из доказанного, что каждая фракция клана КСвыражения Expr(D) не является всталяющей. Значит, Expr(D) удовлетворяет определению псевдосогласующего КСвыражения □

Лемма 1. Пусть M есть детерминированный магазинный автомат. Пусть дуги 7Гь п2 его маршрутов Т = Т1п1Т2, Т1п2 различны. Пусть Т есть накапливающий цикл. Тогда

Л = uj(ni) = и(п2) = Л. Доказательство. Из равенств

beg(n1) = end() = beg(n2)

и из детерминированности автомата следует, что либо п1, п2 различаются своими пометками, либо обе являются стирающими и различаются только своими конечными вершинами.

В первом случае из детерминированности следует, что ) и ш(п2) непусты, и лемма верна.

Во втором случае дуга п1 имеет парную себе в Т1п1, так как Т есть накаплива -ющий маршрут. Но тогда и дуга п2 обязана иметь парную в Т1п2 и, следовательно, end(n2) = end(n1). Таким образом, п2 = п1, т.е. рассматриваемый случай не может возникнуть □

Из леммы 1 следует, что открывающий цикл детерминированного магазинного автомата имеет непустую пометку. Действительно, если Т - накапливающий цикл и маршрут ТТ нейтрален, то Т и некоторый начальный участок маршрута Т удовлетворяют условию леммы 1.

Следующая теорема означает, что для проверки детерминированного мага зинного автомата M на праволинейность достаточно исследовать множество Core(M, 3, 3).

Теорема 2. Если каждый читающий открывающий цикл каждого маршрута Т Е Core(M, 3,3) есть моном, то детерминированный магазинный автомат M праволинеен.

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

Пусть предложение Т автомата M имеет вид

ТГТ1ГТ1 ГТ1 ГТ1ГТ1ГТ1

= Т1П1Т2Т3Т4П2Т5П3Т6,

(П1Т2, Т3, Т4П2Т5П3)

есть гнездо, п1 Т2 и Т7 = Т4п2Т5п3 - циклы, п1, п2, п3 - дуги и ш(п2) = Л. Рас -смотрим маршрут Т = Т1 тпТ2Т3Т4П2Т5П3Т6 Е reduction, тц, Т2п, beg), Т3II, end3), Т411, п2, Т511, п3, Т6), где для j Е {2, 3,4, 5} маршрут Т}II принадлежит

множеству reduction(Tj). Из построения маршрута V следует, что (тг, T3, V), где V = Vп2Vп3, есть гнездо, п1Т2 и V - циклы и пометка последнего цикла непуста. Убедимся, что V является (3,3)каноном, т.е. что в V не может быть больше трех последовательных нейтральных циклов и больше трех "концентри-ческих"гнезд, образованных циклами и обладающих одними и теми же начальной и конечной вершинами.

Пусть участок V маршрута V является нейтральным циклом или гнездом, образованным парными циклами. Тогда, в силу построения маршрута V, Т0 содержит хотя бы один из участков, сохраняемых операцией reduction при переработке V в V. Если V содержит дугу п1 или п3, то он содержит их обе, так как эти дуги парны. Если при этом V является нейтральным циклом, то он не разбивается на два нейтральных цикла; иное противоречило бы построению V или V. Такой нейтральный цикл допустим даже в (1,1)каноне. Если V - гнездо, образованное парными циклами, то вследствие нейтральности V3 и парности дуг п1, п3 наиболее сложный из возможных случаев его устройства характеризуется равенством

TI гтл гтл гтл гтл гтл гтл гтл 0 = 111213042322211

где для 1 < j < 3 V1j и V2j - парные циклы, циклы V11 и V21 содержат соответственно парные друг другу дуги п1 и п3, V22 - дугу п2, V13 или V23 имеет непустой общий участок с V3. Такое гнездо не противоречит определению (3,3)канона.

Пусть теперь V не содержит дуг п1 и п3. Тогда этот маршрут не может иметь общих участков с V или V и расположен в

Если V0 является нейтральным циклом, то, по прежнему, в худшем случае он раз бивается на три нейтральных цикла, из которых один содержит пустой начальный участок маршрута V3!, второй - пустой конечный участок этого маршрута, третий - дугу п2. Если V - гнездо, образованное парными циклами, то ни один из его циклов не содержится целиком в V3! (это противоречило бы нейтральности V3! или тому, что в V3! не может быть парных циклов). Следовательно, наиболее сложный случай устройства гнезда V0 проще, чем рассмотренный выше, и характеризуется равенством

TI гтл гтл гтл гтл гтл

где V1i и V2i - парные циклы для i = 2, 3; они характеризуются как в описанном выше случае.

Итак, V! является (3,3) каноном.

Из леммы 1 следует, что накапливающий цикл n1V2 гнезда (n1V2, V3!, V) яв -ляется читающим. Следовательно, так как V читающий, n1V2 не есть моном в каноне V!, вопреки условию теоремы.

Вполне аналогично рассматривается случай, когда предложение V автомата M имеет вид

Тгтл гтл гтл гтл гтл

= VlПlJ2VзV47Г2J5,

где (71-2, V3, V42) есть гнездо, и V42 - циклы, 7гь П2 - дуги и (2) = Л □

Теорема 2 дает проверяемое по (3,3)ядру (см. алгоритм ниже) условие регулярности детерминированного языка. Это условие не является необходимым. В

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

{u0v0 u Е C+,v Е {a, &}*},

где C есть алфавит n отличных от нуля символов для некоторого натурального n. Здесь мы приведем пример детерминированного магазинного автомата, который является самым, по-видимому, лаконичным из неправолинейных однозначных совершенных детерминированных магазинных автоматов, допускающих регулярные множества. Автомат

({pcPi,p2,Рз, f}, {a, b}, {a, b, Zo}, Zo, 5po, {f}),

где множество 5 состоит из команд

(po, Л, Zo) - (po, Zob), (po, a, b) - (po, ba), (po, a, a) - (po, aa), (po, b, a) - (pi, Л), (pi, a, a) - (pi, Л), (pi,b,b) - (f, Л),

(pi , b, a) - (p2, Л), (p2, Л, a) - (p2, Л), (p2, Л,Ь) - (f, Л), (pi, a, b) - (p3, Л), (p3,a,Zo) - (p3,Zoa), (p3, Л, a) - (p3, Л),

(p3, b, Zo) - (p3, Zob), (p3, Л,Ь) - (f, Л), допускает язык

{ambanb m > l,n > 0}. Каждое предложение этого автомата имеет одну из следующих форм:

(1)m =1:

(a)n> 0: ToniCr1;

(b)n = 0: Toni;

(2)m > 1:

(a)n > m: адСЗвдСГТь

(b)n = m - 1: Т-СЗ1-1;

(c)n = m - 2: ToCC;

(d)0 < n < m - 2: ToC2m-2T2C3nn7C4m-n-3T4,

To = (po,Zo) + (po,b) + (po ,a) ni = (po,a) -a ЬъЬ

П2 = (p1, b)-(Л Z0),п3 = (p1, b)-(pз, Zo),

Ci = (p3,Zo)+a(p3,a)-a(p3,Zo), Ti = (p3,Zo) +(p3,b)-(f,Zo),

C2 = (p0, a) + (pb a),T2 = (p0, a) + (pb a)a)

C3 = (p1, a)-a (p1, a),n4 = (p1, a)-a (p1, b),

T3 = (pb a)-a (p2,n6 = (p2, b)-(f, Z0),

T4 = (p2, a)-Ла(p2, b)n6,П7 = (pi, a)-ba(p2, a),

C4 = (p2,a)-а (p2,a).