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

Пусть 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-11-30