= U L(P,Q)fe+i =

a,b€£

(P,Q)ex

L({Pa,bQ))k=$

= {з1в2 G U L(P,Q) j si = s2 < k + 1} =

(P,Q)6X

= {S1S2 G L(X) j si = S2 < k + 1}

□

Лемма 8. Пусть k > 1; Xb X2 G 2R(M). Тогда

Xi =fe+i X2 Xi =fe X2 Va, b G E L(Xi(a, b))k = L№<a, b))k.

Доказательство. Пусть Xi =k+i X2. По определению отношения кнеразли-чимости L(Xi)k+i = L(X2)k+i. Следовательно, L(Xi)k = L(X2)k. А это значит, что Xi =k X2. Докажем, что

Va,b G E L(Xi(a, b))k = La, b))k.

Допустим противное. Тогда

3a, b G E : Li = L(Xi(a, b))k = L(X2(a, b))k = L2.

Это значит, что найдется цепочка, принадлежащая одному языку и не принадлежащая другому. Пусть, например, существует такая цепочка s G E*, что s G Li и s G L2. Так как s G Li = L(Xi(a, b))k, то asb G L(Xi)k+i. Но по усло -вию Xi =k+i X2, следовательно, L(Xi)k+i = L(X2)k+i. Отсюда получаем, что asb G L(X2)k+i, а это значит, что s G L(X2(a, b))k = L2. Но s была выбрана как цепочка, не принадлежащая L2. Полученное противоречие доказывает, что

Xi =k+i X2 Xi =k X2 Va, b G E L(Xi(a, b))k = L(X2<a, b))k.

Пусть теперь Xi =k X2 и L(Xi(a, b))k = L(X2(a, b))k для любых a, b из алфавита E. По лемме 7

L(Xi)k+i = L(Xi)k U ( J aL(Xi(a, b))kb).

a,b6S L(Xi(a,b))k=0

По условию L(Xi(a, b))k = L(X2(a,b))k для любых a, b из E и Xi =k X2. Последнее означает, что L(Xi)k = L(X2)k. Следовательно,

L(Xi)k+i = L(X2)k U ( J aL(X2(a, b))kb).

a,b6S L(X2(a,b))k=0

Пользуясь леммой 7, получаем, что L(Xi)k+i = L(X2)k+i, т. е. Xi =k+i X2. Таким образом,

Xi =k X2 Va, b G E L(Xi(a, b))k = L(X2<a, b))k Xi =k+i X2

□

Лемма 9. Пусть k > 0. Тогда =k+iC =k.

Доказательство. По лемме 8 из соотношения Xi =k+i X2 следует Xi =k X2. Но это и означает, что =k+iC =k □

Лемма 10. Пусть =k = =k+i для некоторого k > 0. Тогда =k+i= =k+2.

Доказательство. По лемме 8

Xi =k+2 X2 Xi =fe+i X2 Va, Ъ G S

L(Xi(a,b))k+i = L(X2(a, b))k+i-По определению отношения неразличимости это значит, что

Xi =k+2 X2 Xi =k+i X2 Va, Ъ G S

Xi(a, Ъ) =k+i -Ma, Ъ). Но по условию =k = =k+i. Следовательно,

Xi =k+2 X2 Xi =k X2 Va, Ъ G S Xi(a, Ъ) =k X2(a, Ъ).

По лемме 8 получаем, что

Xi =k+2 X2 Xi =k+i

т. е. =k+2 = =k+i П

Заметим, что отношение =0 разбивает 2R(M) на два класса эквивалентности: содержащий терминальные пары и не содержащий таковых. Более формально

Xi =0 X2 ЭР, Q G V(M) : (P, P) G Xi, (Q, Q) G X2

v VP g V(м) (P, р) G Xi и X2.

Заметим также, что по лемме 8

Xi =k+i X2 Xi =k X2 Va,Ъ G S

L(XiM))k = L(X2(a,ty)k. По определению отношения неразличимости

Xi =k+i X2 Xi =k X2 Va, Ъ G S

Xi(a, Ъ) =k X2(a, Ъ).

А это дает следующий способ вычисления отношения =k+i, если вычислено отношение =k.

Для каждой пары (Xi,X2) множеств вершин, такой, что Xi =k X2, для всех a, Ъ G S перебрать пары множеств вершин (Xi(a,,X2(a, Ъ)). Если Xi(a, Ъ) =k X2(a, Ъ) для всех a, Ъ G S, то Xi =k+i X2, иначе Xi =k+i X2.

Из сделанных замечаний и лемм 9 и 10 вытекает корректность следующего алгоритма.

Алгоритм 3. Построение отношения неразличимости.

Вход. Множество P(M) парных дуг автомата M.

Выход. Отношение = неразличимости на 2R(M).

Метод. Вычислить отношение =0, положить k равным нулю; вычислять =k+i и увеличивать k на единицу, пока =k+i = =k; взять в качестве отношения = отношение =k.

Утверждение 3. Алгоритм 3 заканчивает работу.

Доказательство. Конечность построения отношения =0 сомнений не вызывает. Как уже было замечено, отношение =k+1 строится по отношению =k. По лемме 9 =k+1C =k. Это значит, что либо =k+1= =k, либо =k+1C =k. По лемме 10 отношение = построено, когда =k= =k+1. Следовательно, при увеличении к на единицу и построении очередного отношения кнеразличимости либо алгоритм останавливается, либо количество пар множеств вершин, связанных отношением =k, уменьшается. А так как количество пар множеств вершин, связанных отношением =0, конечно, то алгоритм работу закончит □

Сформулируем алгоритм решения проблемы эквивалентности для автоматов из Mi.

Алгоритм 4. Проверка эквивалентности автоматов из M1.

Вход. Автоматы Mi = (K Е, Г;, Zoi, 6upoi, F), i = 1, 2; Ki П K = 0.

Выход. Если L(M1) = L(M2), то "да", иначе "нет".

Метод. С помощью алгоритма 3 построить отношение неразличимости = на

2 (Mi)uv (м2)хУ (Mi)uy (м2).

если множества пар вершин

IJ ((p01,Z0l), (/i,Z01)) fl6Fi

IJ ((p02,Z02), (/2,Z02)) /26F2

неразличимы, то ответить "да", иначе "нет".

Утверждение 4. Алгоритм 4 ответит "да"тогда и только тогда, когда L(M1) =

Доказательство. Действительно, алгоритм 4 ответит "да"тогда и только тогда, когда множества

IJ ((p01,Z01), (/1,Z01)) fi6Fi

IJ ((p02,Z02), (/2,Z02))}

неразличимы, т. е. когда

IJ L((p01,Z01), (/1,Z01))= U L((p02,Z02), (/2,Z02))-

fieFi/262

Из определения языка пары вершин имеем

L(M;)= U L((p0i,Z0i), (/i,Z0i))

/i6FiUF2

для i = 1,2. Следовательно, алгоритм 4 ответит "да"тогда и только тогда, когда

L(M1) = L(M2) □