3.4. k-эквивалентные разбиения

Для целей, которые станут ясными из следующих параграфов, представляет интерес деление или «разбиение» состояний автомата на классы по следующим правилам: (1) все состояния, принадлежащие к одному классу, должны быть k - эквивалентными; (2) все состояния, принадлежащие к разным классам, должны быть k - различимыми. Такое разбиение называется k - эквивалентным разбиением автомата и обозначается Классы называются классами k - эквивалентности и обозначаются и т. д. Состояния, принадлежащие к одному и тому же классу, называются смежными состояниями, состояния, принадлежащие к разным классам, называются разобщенными состояниями.

Рис. 3.3 и таблица 3.2 представляют автомат . Для этого автомата 2 - эквивалентное разбиение имеет вид

Легко проверить по графу переходов автомата А7, что смежные состояния в заданные выражениями (3.1),

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

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

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

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

Доказательство. Предположим, что разбиение состоящее из не является единственным. Тогда для этого же автомата должно быть другое А-эквивалентное разбиение, скажем Р, состоящее из . Пусть . Поскольку состояния из являются k - эквивалентными и поскольку не

Таблица 3.2. Автомат

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

Предположив, что r принимает значения и, получим, что каждому классу в соответствует идентичный класс в Поскольку общее число состояний в должно быть таким же, как в , то должны быть одинаковыми и, следовательно, является единственным.

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

Доказательство. Согласно лемме 3.4 два состояния, являющиеся k - различимыми, являются и -различимыми. Тогда - справедливость доказываемой леммы непосредственно вытекает из определения .

Например, автомата не может содержать такие классы, как поскольку эти классы, как следует из (3.1), содержат состояния, которые в являются разобщенными.

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

Доказательство. Пусть будут различимыми k - эквивалентными состояниями автомата М и пусть входная

последовательность будет наикратчайшей входной последовательностью, различающей состояния . Это значит, что вырабатывают различные выходные символы не раньше, чем будет приложен входной символ Поскольку являются k - эквивалентными, то должно быть . Пусть преемниками по отношению к входной последовательности будут соответственно; так как то и эти преемники всегда существуют. Тогда могут быть различимы при входной последовательности длина которой равна Эти два состояния не могут быть различимы с помощью никакой другой более короткой последовательности, так как это противоречило бы условию, что являются -эквивалентными. Следовательно, , являются k - эквивалентными, но -различимыми. Лемма доказана. Рассмотренная ситуация иллюстрируется на рис. 3.4.

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

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

два состояния, которые являются k - эквивалентными, но Следовательно, должно содержать два смежных состояния, которые становятся разобщенными в . Таким образом, если смежные состояния в каком-нибудь классе из являются различимыми, то разбиение должно отличаться от разбиения . Если отличается от , то, согласно лемме 3.6, должно существовать «собственное разделение» которое должно получаться расщеплением одного или нескольких классов на два или более подклассов. В заключение можно утверждать следующее.

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

Для автомата например, имеем:

которое является собственным разделением

которое является собственным разделением Однако видно, что

совпадает с и, следовательно, смежные состояния в каждом классе являются эквивалентными.