Рассмотрим маршрут

T = T0niT[n2T2 € reduction(T0, я, Ti, п2, T2).

Маршрут T[, полученный редуцированием нейтрального маршрута Ti, является нейтральным. Таким образом, ni и п2 парны в T.

Убедимся, что T является каноном. Заметим, что T0, T и T22 не содержат нейтральных и парных циклов. Следовательно, в T каждый участок T3, который является нейтральным циклом или гнездом, образованным парными циклами, содержит какуюлибо из дуг ni, п2. Но тогда T3 содержит обе эти дуги, так как они парны, а T3 нейтрален. Отсюда выводим, что если T3 - нейтральный цикл, то он не разбивается на два (и тем более на три) нейтральных цикла, а если T3 - гнездо, то это простое гнездо. Таким образом, T удовлетворяет определению (1,1)канона □

Пусть далее везде, где это не оговаривается специально, под автоматом M понимается автомат (K, Е, Г, Z0,5,p0,F) из Mi.

Назовем пару (P, P) € R(M) терминальной парой вершин.

Назовем языком пары вершин (P, Q) € R(M) следующее множество цепочек: L(P, Q) = {sis2 j множество {Psi,s2Q) содержит хотя бы одну терминальную пару вершин}.

Из этих определений следует, что для любого автомата M

L(M)= J L((p0,Z0), (/,Z0)).

Для любого элемента ф = (si, s2) € Ф множество

J((p0,Z0)si,s2(/, Z0)) f 6F

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

Алгоритм 2. Проверка допустимости цепочки.

Вход. Автомат M, цепочка s.

Выход. Если s € L(M), то "да", иначе "нет".

Метод. Если длина цепочки s нечетна, то "нет"; если s = Л, то если p0 € F, то "да", иначе "нет"; построить множество

X = U ((p0,Z0)si,s2(f, Z0)), f 6F

где sis2 = s, si = s2; если X содержит хотя бы одну терминальную пару вершин, то "да", иначе "нет".

Определим некоторые понятия, двойственные к уже введенным. Пусть X, X , X2 С R(M); ai, а2 € Е; Pi, P2, Qi, Q2 € V(M); ф, фъ Ф2 € Ф.

Определим функцию А1 : 2R(M) х Ф -> 2R(M) следующим образом: AMi(AMi(X, ф1), Ф2) = AMi(X, Ф1Ф2),

AMi(X,£)= X,

А-м1(Х1иХ2,ф) = AM1(X1 ,ф) U А-м1(Х2,ф),

АмЧ0,ф) = 0,

AM1({(Pi,Qi)>, (ai,fl2)) = {(2,2) I (Pi,Qi) e(P2ai,a2Q2)}.

Введем сокращения, аналогичные принятым для Ам. Пусть X, Y С R(M), ф = (s1, s2) е Ф, Y = А-1(Х, ф). Тогда будем писать Y = X-1ф и Y = X-1 (s1,s2). Если X = {(P1, P2)}, то также возможна запись Y = (P1s1, s2P2)~l.

Из определений Ам и А-1 вытекает справедливость следующей леммы.

Лемма 6. Пусть X, Y С R(M); X, Y = 0; ф е Ф. Тогда, если Y С Xф, то Y-1ф п X = 0, и если X С Y-1ф, то Xф П Y = 0 □

Назовем обратным языком пары вершин (P, Q) е R(M) следующее множество: L-1(P,Q)={siS2 1 3/eF:((po,Zo), (/, Z0))e{Psi, S2Q)-1}.

Утверждение 2. L(M) = U L-1(P,P).

(P,P )6R(M)

Доказательство. Сначала докажем соотношение

L(M) С J L-1(P,P).

(P,P )6R(M)

По определению функции Ам для любой цепочки s е L(M), s = s1s2, s1 = s2, найдутся такая терминальная пара вершин (P, P) е R(M) и такое заключительное состояние / е F, что (P, P) е ((po, Z0)si5 s2(f, Z0)). По лемме 6 это значит, что

((po,Zo), (f,Zo)) e(Psl,S2P

Следовательно,

sis2 е L-1(P,P).

Таким образом,

Vs е L(M) 3(P, P) е R(M) : s е L-1(P, P). А это означает, что

L(M) С J L-1(P,P). (p,p )егс(м)

Теперь докажем, что

U L-1(P,P) С L(M). (p,p )егс(м)

(P,P)),

s е L-1(P, P), s = sis2, si = s2 .

По определению функции А-м1 найдется такое состояние / е F, что

((po,Zo), (f,Zo)) e(Psl,S2P Следовательно, в силу леммы 6

(P,P) еОг)/)).

А это значит, что

S1S2 е L(M),

V(P, P) е R(M) Vs е L-1(P, P) s е L(M).

Следовательно,

(J L-1(P,P) С L(M)

(P,P )6R(M)

и, в силу доказанного ранее,

L(M )= J L-1(P,P) (p,p )ея(ы)

□

Пусть X е 2R(M). Назовем языком множества пар вершин объединение

L(X )= U L(P,Q).

(P,Q)eX

L(X)k = {S1S2 е L(X) j s11 = s21 < k}. Назовем L(X)k k-подмножеством языка L(X).

Пусть L(X1)k = L(X2)k, где X1, X2 е 2R(M), k > 0. Тогда будем называть множества X1 и X2 k-неразличимыми и писать

Если X1 и X2 kнеразличимы для любого k > 0, то будем говорить, что они неразличимы, и писать

X1 = X2.

Отношения =k и = назовем отношениями k-неразличимости и неразличимости соответственно.

Лемма 7. Пусть X е 2R(M). Справедливо следующее соотношение: L(X)k+1 = L(X)k U ( J aL(X(a, 6»kb).

a,b£Y, L(X (a,b»fc =0

Доказательство. По определению языка множества пар вершин язык L(X)k+1 состоит из всех цепочек множества L(X), длина которых не превосходит 2(k +1). Цепочки множества L(M), длина которых не превосходит 2k, по определению образуют множество L(X)k. Убедимся, что

(J aL(X (a,6»k b

a,b6S L(X (a,b»fc=0

содержит все цепочки из L(X), имеющие длину 2(k + 1). Действительно: (J aL(X (a,b»k b = J aL((Pa,bQ))k b =

a,b6Sa,b6S

L(X (a,b»fc=0(P,Q)6X

L((Pa,bQ»fc=0