Доказательство. Рассмотрим маршрут

T = T[n1T22n2T3 G reduction(Ti, п1, T2, п2, T3).

Он, как и T1n1T2n2T3, является предложением, так как удаление из маршрута нейтральных и парных циклов, осуществляемое операцией reduction, сохраняет его заряд и пару концов. По той же причине (n1,T22,п2) является гнездом маршрута T. Предоставляем читателю проанализировать возможные положения в T нейтральных и парных циклов и убедиться, что это (1,1)канон □

Теорема 4 (о развитии маршрутов). Пусть D есть некоторый Dграф. Для каждого его нейтрального маршрута T существует такой канон T0, что (T0,T) G §*D. Для каждого элемента (Tb T2, T3, T4, T5) родословной маршрута T с предком T0 маршрут T2T3T4 содержится в некотором каноне из Core(D, 2,1).

Доказательство. Достаточно рассмотреть производные маршруты. Пусть T - производный маршрут Dграфа D. По лемме 4 T содержит формант. Следовательно, возможны два случая:

(i)T = T1T2T3 и T2 есть формантцикл (тогда (T1T3,T) Gb);

(ii)T = T{T2T3T4T5 и T2T3T4 есть формант с парными в нем циклами T2, T4 (тогда (TiT3T5, T) gd). В любом случае имеем такой маршрут T, что (TT) GffD. Так как T < T , существует последовательность T0,..., Tk, такая, что k > 0, T0 не содержит нейтральных и парных циклов, Tk = T, (Ti 1, Tj) Gfr> для i = 1,... ,k. Итак, (T0,T) GffD, T0 является каноном, и первая часть теоремы верна. Вторая часть следует из леммы 5 □

Ядро Dграфа, построенного по магазинному автомату M, будем называть также ядром магазинного автомата M и обозначать через Core(M).

Пример 9. Пусть C есть подмножество (1,1)ядра Dграфа D2, рассмотренное в примере 5. Его элемент

T = (1223467898)

содержит формантгнездо (2234) и формантцикл (98). Циклический участок (89), имеющий заряд -а+а, не является формантом. У маршрута T два непосредствен -

ных предка: Ti = (12367898) и T2 = (12234678). T3 = (123678) - общий предок

маршрутов T1 и T2. Кроме маршрутов T, T1, T2, T3, в C входит маршрут (157898) и его единственный предок (1578), совсем не содержащий циклов. Легко видеть, что (w, d)ядро рассматриваемого Dграфа, где w или d больше единицы, не определяет новых формантов.

Теорема о развитии означает, что ядро D графа D выражает закон образования цепочек языка L(D) из некоторых подцепочек пометок маршрутов, входящих в ядро.

§2. О морфических представлениях бесконтекстного языка

Понятие D графа позволяет сравнительно легко получить теорему о морфиче ском представлении бесконтекстного языка, которая перекликается с теоремой ХомскогоШютценберже. Последняя выводится из нашей как простое следствие. Формулировка и доказательство нашей теоремы обобщают таковые для известной

теоремы о представлении регулярного языка морфическим образом локального языка [Salomaa 81].

Докажем нашу теорему конструктивно. При этом потребуется построение по Dграфу некоторых специфических локального языка и Dязыка. В целях этого построения введем несколько обозначений и докажем несложные леммы об условиях соединимости дуг и нейтральных маршрутов в большем маршруте. Входной D граф обозначается через

D = (V, Е, P,A,Pc,F).

Напомним, что множество нейтральных маршрутов Dграфа D является подмножеством Dязыка Lp.

Пусть А - алфавит, x £ А+, x = ay = zb для некоторых a,b £ A, y,z £ А*. Тогда

first(x) = a, last(x) = b.

Пусть цепочка дуг пп является маршрутом. Тогда будем называть эти дуги соединимыми (в порядке пп). Будем также говорить, что (п, п) есть пара соединимых дуг.

Важно отметить, что для построения всех пар соединимых дуг достаточно рас смотреть (2,2)ядро Dграфа D. Действительно, для каждого успешного маршрута ТпгТг, где (п1,п2) £ P, любой элемент множества

reduction(Ti, п1, endi), п2, T2)

является, самое большее, (2,2) каноном.

Непосредственно из определений Dмножества P, маршрута Dграфа и соединимых дуг получаем следующие две леммы.

Лемма 7. Пусть (п1,п2) £ P и T - нейтральный маршрут. Пусть

(п1, first(T)) и (lastiT), п2)

суть пары соединимых дуг. Тогда п1Tп2 является нейтральным маршрутом □

Лемма 8. Пусть T1 и T2 - непустые нейтральные маршруты и

(last(Ti), first(T2))

есть пара соединимых дуг. Тогда T1T2 является нейтральным маршрутом □ Пусть E = E(D). Пусть

A = {п £ E\Ьед(п) = Po},

B = {п £ E\епЛ(п) £ F)}, C = {пп £ E2 не является маршрутом}.

R = (AE* П E*B) - E*CE*

является локальным языком.

Как показывает следующий пример, последовательность п1п2 дуг, удовлетворя -ющих равенству end) = Ьед(п2), не обязательно является маршрутом.

Пример 10. Граф совершенного магазинного автомата

(0>о>рьp2,рз}, {a, b}, {Zo, a}, Zo, 8,ро, {р3}), где множество 8 состоит из команд

(ро, a, Zo) - (ро, Zoa),

(ро, a, a) - (ро, aa),

(ро,b, a) - (рl, Л),

(р1,b, a) - (рl, Л), (р1, Л, Zo) - (р2, Zoa),

(р2, Л,a) - (рз, Л),

имеет Эмножество

{(1,4), (1, 6), (2, 3), (2, 5), (7, 8)}.

Л(1) = 0?o,Zo)aO?o,a),

Л(2) = (ро, a)a(рo, a),

Л(3) = (ро ,a)b(рl,a), Л(4) = (ро, a)b(рl, Zo),

Л(5) = (р1 ,a)b(рl,a), Л(6) = (рро),

Л(7) = (р1,Z0)Л(р2,a),

Л(8) = (р2,a)Л(рз,Zo). Последовательность (2,4) удовлетворяет условию end(2) = beg(4), но не является маршрутом, так как вершина (р1, Zo) не может быть конечной вершиной маршрута с начальной памятью (ро, +a).

Лемма 9. Пусть x = uvw G Lp П R, Л = v G LP. Тогда v является нейтральным маршрутом.

Доказательство. Индукцией по длине m непустой скобочной подсистемы v.

При m = 2 утверждение следует из определения локального множества R.

Пусть k > 1. Предположим, что утверждение верно для всех скобочных подсистем, длина которых не меньше двух и не больше 2(k - 1), и рассмотрим в цепочке x скобочные подсистемы длины 2k. Возможны следующие два случая.

Случай 1. Скобочная подсистема длины 2k имеет вид ayb, где (a, b) G P и y является скобочной системой. По предположению индукции y является нейтральным маршрутом. Из соотношения x G Lp П R следует, что цепочка y и пара (a, b) удовлетворяют условиям леммы 7. Следовательно, ayb есть нейтральный маршрут.

Случай 2. Скобочная подсистема длины 2k имеет вид yz, где y и z сами являются непустыми скобочными системами. По предположению индукции y и z яв -ляются нейтральными маршрутами. Так как yz - подцепочка цепочки x G Lp ПR, пара (last(y), first(x)) есть пара соединимых дуг. Но тогда yz является нейтраль -ным маршрутом по лемме 8 □

Теорема 5. Пусть T G Lp. T является непустым успешным маршрутом тогда и только тогда, когда T G R.