3.2.5.1.Разделение Эграфа, обусловленное отношением сцепленности.

Пусть T е Computations(p, P,Q,w). В простейшем случае среди вершин маршрута T нет вершин итерантов. Тогда T е Lines(p, P,Q,w).

Если какаялибо из вершин маршрута T является вершиной итеранта, то его можно представить последовательностью T0T1T2, где T0 не содержит дуг итерантов, пара pair(Ti) образована вершинами сцепленных итерантов, T2 не содержит дуг итерантов, сцепленных с представленными в T1 итерантами.

Тройку (T0,T1,T2) обозначим через fi(p,T). Из определений итеранта и сцеп-ленности итерантов следует единственность такого разложения маршрута T.

Пусть C - класс, содержащий итеранты с вершинами beg(T1), end(T1). Участку T2 сопоставим лоскут

Rest(D, T2) = (D,E(D), P - {(nl,n2) eP(C)дуга п или n

не является линейной}, {beg(T2)}, {end(T2)}).

Заметим, что в случае пустоты участка T2 лоскут Rest(D, T2) не имеет непустых предложений. Действительно, при beg(T2) = end(T2) = P непустой нейтральный маршрут с парой концов (P, P) является Rвставкой. Значит, участвующие в нем пары D множества входят в P(C) и состоят из дуг, которые не являются линей ными. Следовательно, рассматриваемый маршрут не может быть предложением лоскута Rest(D, T2). Таким образом,

Sentences (Rest (D,T2)) = {beg(T2)}

при пустом T2 и язык L(Rest(D, T2)) всегда непуст.

D множество лоскута Rest(D, T2) нельзя определять как P - P(C). Следую щий пример показывает, что P(C) может вовлекать линейные дуги Dграфа D, участвующие во вставках, определяемых некоторым классом C = C.

Пример 16. Рассмотрим Dграф

1 О 36 О 8

-О О-О-О О-

1 О 36 О 8

с D множеством

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

Его итеранты образуют два класса сцепленности, каждый из которых определяет S вставки, использующие одну и ту же пару линейных дуг (4, 5).

3.2.5.2.Разложение секущей и основной алгоритм. Ограничимся далее ней -тральными атомами и вставками.

Пусть T е Across(C, P,Q,w). Пусть T - нейтральный участок секущей T, который нельзя увеличить (за счет соседних участков), не нарушая его нейтраль ности. Назовем такой участок звеном. Обозначим через Segmentations(T) мно -жество всех последовательностей вида T0T1 T1...TjcTk, где для 1 < i < к T есть

атом, для 0 < j < к Tj не содержит атомов или пуст и Tj непуст, если Tj = Tj+1 есть Ратом.

Последнее требование обеспечивает конечность множества Segmentations(T).

Для каждого звена T построим с помощью множества Segmentations(T) совокупность всех "потомков" звена, удовлетворяющих определению (1,2)канона, и расставим в каждом потомке именованные скобки по принципу, изложенному в параграфе 1.3 при определении так называемой схемы фразы. Обозначим результат расстановки скобок в t через scheme(t). Пусть

Schemes(T) = {scheme(t)\t является (1,2)каноном; (T,t) £ f*}.

Пусть T - секущая, T1,Tl - все ее звенья. Обозначим через o(T) множество {toaiti...aiti\ toTiti...T,,ti = T; Oi £ Schemes(T)}.

Заметим, что участки tj, 0 < j < l, секущей T определяются единственным образом. Обозначение o(T) имеет смысл и при отсутствии в T звеньев, то есть при l = 0. Тогда t0 = T, o(T) = {T}.

Алгоритм построения КСвыражения E(D) обозначим так же, как искомое выражение. Можно считать его функцией, отображающей Эграфы в КС-выражения. Значение функции вычисляется рекурсивным образом.

Алгоритм 7. Преобразование Эграфа в КСвыражение, управляемое фактормножеством на множестве итерантов по отношению сцепленности.

Вход. Эграф D = (V, Е, P, X, Po, F).

Выход. КСвыражение E(D).

Вспомогательные обозначения.

<£(D) = {fi(T)\ T £ Lines(P ,Po,Q, Л); Q £ F};

Straight(D) = {T £ Lines(P, P0, Q, Л)\ Q £ F; T - не имеет вершин итерантов

Метод. Положить E(D) равным

Е T + ЕЕ o(T))E (Rest(D,T2))].

Т&Straight{D)(f0 ,T,1,T2)&(D) T&Across{rI1)

Теорема 11. Пусть D - Эграф или лоскут. Тогда L(E(D)) = Sentences(D). Доказательство. Индукцией по числу классов сцепленности. Если таковые отсутствуют, то

Sentences(D) = Straight(D),

E(D) = Е T;

Т eSentences(D)

таким образом, теорема в данном случае верна.

Пусть D имеет классы сцепленности. Тогда $(D) = 0. Заметим, что каждое предложение, не принадлежащее Straight(D), можно представить в виде T0TiT2, где для некоторых Tb T2 тройка (T0,Ti Д) £ <(D) и (fi,T) £ ft*D для i = 1, 2.

Маршрут T0 способен развиваться разве только за счет своей конечной вер -шины, что можно игнорировать, так как эту вершину end(T0) = heg(T1) можно отнести и к T. Следовательно, входящая в E(D) сумма по элементам множества $(D) задает все способные к развитию предложения, если подвыражение 12,

T&Across(T,1)

£2 = E (Rest(D,f2)),

задает все маршруты с парой концов (Ьед(Т), end(f2)) и зарядом p(rf1rf2). Согласно параграфу 1.3 £1 задает множество Computations(V(C),Т1). По предположению индукции £2 задает множество Sentences(Rest(D,T2)), представляющее все маршруты с парой концов pair(f2) и зарядом р(гГ2). Следовательно, теорема верна

□