3.5. Эквивалентные разбиения

k - эквивалентное разбиение автомата М называется эквивалентным разбиением М и обозначается P, если во всех классах этого разбиения смежные состояния эквивалентны. При этих условиях каждый класс разбиения называется классом эквивалентности. Из материалов § 3.4 следует, что P является наиболее детальным разбиением По теореме 3.4, эквивалентное разбиение P может быть получено, если образовывать для до тех пор, пока первый раз получится разбиение, которое совпадает с предыдущим разбиением. Это разбиение и будет P. Пусть равенство означает, что являются одинаковыми разбиениями, и пусть обозначает число классов в Используя это обозначение, предыдущие результаты могут быть обобщены следующим образом:

Если

Если все n состояний автомата являются 1 - эквивалентными, то разбиение состоит из одного класса, содержащего n состояний. Очевидно, что если все n состояний являются 1 - эквивалентными, то их первые преемники по отношению к любой входной последовательности являются также 1 - эквивалентными. Таким образом, все n состояний должны быть 2 - эквивалентными и, следовательно, . Тогда, по ( 3.6), и все n состояний являются эквивалентными. Для автомата такого типа является одинаковой для всех и, следовательно, . Тогда по определению, введенному в § 1.6, можно утверждать, что автомат, в котором все состояния эквивалентны, является тривиальным автоматом. В дальнейшем, если не будет специально оговорено, будут рассматриваться только нетривиальные автоматы, т. е. автоматы, в которых имеется, по крайней мере, одна различимая пара состояний или в 1 - эквивалентных разбиениях которых имеется, по крайней мере, два класса.

Лемма 3.8. Если , то

Доказательство. Если то, по (3.5) и (3.6), для . Поскольку , то (3.7) следует по индукции.

Лемма 3.9. Если для автомата с n состояниями то число состояний в каждом классе разбиения не превышает

Доказательство. Согласно лемме 3.8, число классов в равно, по крайней мере, Предположим, что один класс содержит больше чем n — k, скажем состояний. Тогда, поскольку каждый другой класс в должен содержать, по крайней мере, одно состояние, общее число состояний в будет не менее Лемма доказана, так как общее число состояний не может превосходить n.

Лемма 3.10. Для автомата с n состояниями

Доказательство. Если то, согласно лемме 3.8, Так как число классов в k - эквивалентном разбиении автомата с n состояниями не может превышать n, то полученное противоречие доказывает лемму.

Из леммы 3.10 и уравнения (3.6) можно вывести следующее заключение:

Теорема 3.5. Для автомата с n состояниями

Таким образом, процесс определения P для автомата с n состояниями путем последовательного построения для k = l, 2, 3 требует не более n-1 построений.

Другим вариантом формулировки теоремы 3.5 является

Следствие 3.1. Два состояния автомата с состояниями эквивалентны, если они (n - 1)- эквивалентны, и различимы, если они -различимы.

Определение может быть определено с помощью следующего правила: состояния являются смежными в тогда и только тогда, когда они для каждого входного символа дают одинаковые выходные символы.

Определение . Пары смежных состояний в которые при любом входном символе переходят

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

Рассмотрим, например, разбиение для автомата приведенное в (3.2). Первые преемники состояний 1, 3 и 8 являются смежными в при подаче а или и в 231 при подаче у. Первые преемники состояний 5 и 7 являются смежными в если приложен входной символ а, в если приложен символ p, и в если приложен символ у. Следовательно, являются классами Первые преемники состояний 2 и 4 по отношению к каждому входному символу являются смежными состояниями в поэтому являются классом Одноэлементные классы переходят в без изменений. Полученное разбиение будет таким, как показано в (3.3).

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