Доказательство. Если qi rk+1 qj, то qi и qj неотличимы на входных словах, длина которых не превосходит k+

Лемма 2

Лемма доказана.

Доказательство

Если q _i r_k+1 q _j, то q _i и q _j неотличимы на входных словах, длина которых не превосходит k + 1. Поэтому q _i и q _j неотличимы и на dc[ словах длины k. Следовательно, r_k r_k+1.

Если q _i e q _j, то состояния q _i и q _j - неотличимые на всех словах, в том числе на словах, длина которых не превосходит k. Поэтому r_k e.

Если для некоторого числа k справедливо равенство r_k = r_k+1, то r_k = e.

Пусть r_k = r_{k+ 1} . Покажем, что r_k+1 = r_{k+ 2} . То есть если состояния q _i и q _j являются (k + 1) -неотличимыми, то они являются и (k + 2) -неотличимыми.

Пусть a - это произвольное входное слово длины k + 2, начинающееся с символа a. Тогда после переработки первого символа этого слова из состояний q _i и q _j как начальных автомат Á переходит в новые состояния q _{i 1} и q _{j 1}, которые являются k- неотличимыми.

Так как r_k = r_k+1и q _{i 1} r_k q _{j 1}, то по условию леммы q _{i 1} r_k+1 q _{j 1}. Поэтому слово из состояний q _{i 1} и q _{j 1} будет перерабатываться в одно и то же выходное слово. Следовательно, произвольное входное слово a из состояний q _{i 1} и q _{j 1} перерабатывается в одно и то же выходное слово.

Следовательно, q _i и q _j являются k + 2 -неотличимыми.

Поэтому r_k+1= r_k+2.

Повторяя проведенные рассуждения, можно показать, что r_k+1 = r_k+2 = r_k+3 = r_k+4...

Следовательно, для любого входного слова значения () и () равны, т.е. q _i и q _j являются неотличимыми состояниями.

Поэтому, если состояния q _i и q _j неотличимы на словах длины k, то они неотличимы на словах любой конечной длины, т.е. q _i и q _j являются неотличимыми.

Следовательно, r_k = e.

Дата добавления: 2015-03-31