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

Рассмотрим последовательность отношений
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.

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

МИНИМАЛЬНЫЕ АВТОМАТЫ

ОПРЕДЕЛЕНИЕ

Автоматы Á ₁ = (A, B, Q ₁, j₁, y₁) и Á ₂ = (A, B, Q ₂, j₂, y₂) называются эквивалентными, если выполняются соотношения:

1) " q _r Î Q ₁ $ q _s Î Q ₂();

2) " q _s Î Q ₂ $ q _r Î Q ₁().

То есть два автомата являются эквивалентными, если каждое состояние любого из них неотличимо от некоторого состояния другого автомата.

Упражнение

1. Показать, что автоматы Á ₁ и Á ₂ эквивалентны тогда и только тогда, когда множества функций, вычисляемых этими автоматами из различных состояний как начальных, совпадают.

2. Показать, что всякий автомат эквивалентен самому себе.

ОПРЕДЕЛЕНИЕ

Автомат, все состояния которого являются отличимыми, называется минимальным автоматом.

Пусть Á = (A, B, Q, j, y) - некоторый автомат.

Обозначим как j* функцию j*: A ^* Q Q, которая для любого входного слова и состояния q _i принимает значение, равное состоянию Á после переработки из начального состояния q _i.

Эта функция может быть определена следующими соотношениями:

1) " a Î A (j*(a, q _i) = j(a, q _i));

2) " Î A ^*, a Î A (j* ( a, q _i) = j(a, j*(, q _i))).

Замечание. Функцию j* можно использовать для определения функций, вычисляемых автоматами.

Функция может быть задана соотношениями:

1) " a Î A ( (a) = y(a, q _i));

2) " Î A ^*, a Î A ( ( a)= () y(a, j*(, q _i)).

Лемма 4

Если состояния q _i и q _j автомата Á неотличимые, то для всякого входного слова состояния j*(, q _i) и j*(, q _j) также являются неотличимыми.

Дата добавления: 2015-11-30