являются 2-эквивалентными, а разобщенные состояния являются 2-различимыми. Ни одно состояние автомата Л7 не является 2-эквивалентным состоянию 9 (за исключением самого состояния 9), и, следовательно, состояние 9 образует класс, состоящий из одного состояния, - одноэлементный класс.

(o:/rjN(pm

Рис. 3.3. Автомат А1.

Ясно, что ни одно состояние не может принадлежать одновременно двум различным -эквивалентным классам, поскольку это означало бы, что это состояние является &-раз-личимым по отношению к самому себе. Следовательно, общее число состояний в равно общему числу состояний

в автомате.

Лемма 3.5. k-эквивалентное разбиение автомата единственно.

Доказательство. Предположим, что разбиение Р, состоящее из 2*, Sft, Sft , не является единственным. Тогда для этого же автомата должно быть другое А-эквива-лентное разбиение, скажем Рк, состоящее из 2/,, ... • Пусть S4=r{ar, Ог, OrJ. Поскольку состоя-

ния из являются -эквивалентными и поскольку не

имеется ни одного состояния вне 2, являющегося эквивалентным какому-либо состоянию из 2, то в должен быть класс состояний, скажем 2,, состоящий из состояний Ог,,

Or.....и не содержащий никаких других состояний.

Предположив, что г принимает значения 1,2.....м, получим,

что каждому классу в соответствует идентичный класс в Pft. Поскольку общее число состояний в должно быть таким же, как в Р*, то Р и Р должны быть одинаковыми и, следовательно, Р является единственным.

Лемма 3.6. Состояния, являюш,иеся разобщенными в Pj, должны быть разобщенными в P+i-

Доказательство. Согласно лемме 3.4 два состояния, являющиеся /-различимыми, являются и (--1)-различимыми. Тогда - справедливость доказываемой леммы непосредственно вытекает из определения Р и P+i-

Например, Р3 автомата Л7 не может содержать такие классы, как {1, 3, 6) и {2, 5, 9}, поскольку эти классы, как следует из (3.1), содержат состояния, которые в Pj являются разобщенными.

Лемма 3.7. Если автомат М имеет два различимых, но k-эквивалентных состояния, то он также должен иметь два состояния, которые являются k-эквивалентными, но (k-\-l)-различимыми.

Доказательство. Пусть о,- и Oj будут различимыми

-эквивалентными состояниями автомата М и пусть входная

Таблица 3.2

Автомат А1

Рис. 3.4. Иллюстрация к лемме 3.7.

Предположим теперь, что смежные состояния в каждом классе эквивалентности разбиения Р/ являются эквивалентными. Тогда ясно, что Я+ц совпадает с Р,, для всех неотрицательных целых и. Если два смежных состояния в являются различимыми, то они представляют собой два различимых состояния, которые являются -эквивалентными. В этом случае, согласно лемме 3.7, автомат должен иметь

последовательность Infih • • - Ц будет наикратчайшей входной последовательностью, различающей состояния и Oj. Это значит, что О; и Оу вырабатывают различные выходные символы не раньше, чем будет приложен входной символ л. Поскольку О; и Оу являются -эквивалентными, то должно быть lyk. Пусть (/ - k - 1)-ми преемниками и Оу по отношению к входной последовательности Ih

будут al и о, соответственно; так как / > то / ~ k - 10, и эти преемники всегда существуют. Тогда и Оу могут быть различимы при входной последовательности •. •

. . . й, длина которой равна / - (/ - k - \) = k-\-\. Эти

два состояния не могут быть различимы с помощью никакой другой более короткой последовательности, так как это противоречило бы условию, что О; и Оу являются -эквива-

лентными. Следовательно, и Оу являются -эквивалент-

пыми, но (&--1)-различимыми. Лемма доказана. Рассмотренная ситуация иллюстрируется на рис. 3.4.