Определение

Состояния q_i и q_j автомата  называются k-неотличимыми, если q_i и q_j неотличимы на входных словах, длина которых не превосходит k.

То есть q_i и q_j k-неотличимы, если

 ((   k )  ( ( ) = ( ))).

Обозначим как _k  отношение k-неотличимости состояний заданного автомата, т.е. q_i _k q_j тогда и только тогда, когда q_i и q_j являются k-неотличимыми.

Отношение неотличимости состояний  будем обозначать как .

Последующие рассуждения проводятся в предположении, что задан произвольный, но фиксированный автомат, для которого определены отношения  и _k, k = 1, 2, . . .

Упражнение. Показать, что отношение  и отношения _k, k = 1, 2, . . . , являются отношениями эквивалентности на множестве состояний автомата .

Лемма 1

Для всякого значения k справедливы включения:

_k  _k+1 и _k .

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

Если q_i _k+1 q_j, то q_i и q_j неотличимы на входных словах, длина которых не превосходит k+1. Поэтому q_i и q_j неотличимы и на dc[ словах длины k. Следовательно, _k _k+1.

Если q_i  q_j, то состояния q_i и q_j  неотличимые на всех словах, в том числе на словах, длина которых не превосходит k. Поэтому _k .

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

Лемма 2

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

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

Пусть _k = _k+1. Покажем, что _k+1 = _k+2. То есть если состояния q_i и q_j являются (k + 1)-неотличимыми, то они являются и (k + 2)-неотличимыми.

Пусть a  это произвольное входное слово длины k + 2, начинающееся с символа a. Тогда после переработки первого символа этого слова из состояний q_i и q_j как начальных автомат  переходит в новые состояния q_i1 и q_j1, которые являются k-неотличимыми.

Так как _k = _k+1 и q_i1 _k q_j1, то по условию леммы q_i1 _k+1 q_j1. Поэтому слово из состояний q_i1 и q_j1 будет перерабатываться в одно и то же выходное слово. Следовательно, произвольное входное слово a из состояний q_i1 и q_j1 перерабатывается в одно и то же выходное слово.

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

Поэтому _k+1 = _k+2.

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

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

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

Следовательно, _k = .

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

Лемма 3

Разбиение множества состояний автомата, порождаемое отношением _k+1, является подразбиением разбиения, порождаемого _k.

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

Очевидно, что если два состояния являются (k+1)-неотличимыми, то они являются и k-неотличимыми.

Поэтому всякий класс (k+1)-неотличимых состояний является частью некоторого класса k-неотличимых состояний.

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

ТЕОРЕМА 7.4

Если q_i и q_j  отличимые состояния автомата , имеющего n состояний, и  кратчайшее слово, на котором различаются эти состояния, то | | n  1.

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

Рассмотрим последовательность отношений k–неотличимости состояний автомата : ₁, . . . , _k, . . .

Поскольку  имеет отличимые состояния, то ₁ разбивает множество состояний  не менее чем на два класса 1-неотличимых состояний. (В противном случае все состояния  являются неотличимыми, поскольку 1 – неотличимость всех сотояний автомата означает, что значения функции выхода зависят только от входных символов.)

Согласно лемме 3, если _i  _i+1, то число классов (i+1)-неотличимых состояний автомата хотя бы на 1 больше числа классов i-неотличимых состояний.

Поскольку автомат имеет n состояний, то найдется такое значение i < n, что справедлива цепочка включений:

₁ ... _{i  1} _i = _i+1 . . .

Справедливость последнего свойства следует из того, что каждый элемент разбиения множества состояний  на множества i-неотличимых состояний должен содержать хотя бы одно состояние.

Следовательно, _i = .

Поэтому, если состояния q_i и q_j являются отличимыми, то они должны различаться хотя бы на одном слове, длина которого не превосходит n  1.

Доказательство окончено.