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

ТЕОРЕМА 7.4

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

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

Лемма 3

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

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

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

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

Если q _i и q _j - отличимые состояния автомата Á, имеющего n состояний, и - кратчайшее слово, на котором различаются эти состояния, то | | n - 1.

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

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

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

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

r₁ ... r _{i - 1} r _i = r _{i +1} ...

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

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

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

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