§3.4. Приведённый автомат

Назовём состояния и автомата неотличимыми, если для всех Состояния и отличимы, если при некотором Положим если и неотличичимы.

Нетрудно видеть, что отношение неотличимости ~ на множестве

состояний автомата

является отношением эквивалентности. Это отношение вызывает разбиение множества

на непересекающиеся классы эквивалентности:

При этом любые два состояния

лежащие в одном классе, неотличимы, а любые два состояния из разных классов отличимы.

Множество классов отношения ~ (фактор-множество обозначим через Построим новый автомат В качестве входного и выходного алфавитов автомата возьмём те же множества и которые были у автомата а в качестве множества состояний возьмём множество Надо определить теперь функции и

Пусть Наиболее естественным является следующее определение значения взять какой-нибудь элемент принадлежащий классу найти а затем класс, в котором лежит элемент объявить значением То есть считать, что

(1)

Докажем корректность этого определения, т.е.

независимость от выбора представителя в классе эквивалентности. Пусть

Определение будет некорректным, если окажется, что

Докажем, что определение корректно. Если

то

при некотором

Это означает, что

Следовательно,

что противоречит условию. Итак,

поэтому определение (1) корректно.

Функцию определим на по формуле

(2)

По определению неотличимости состояний мы имеем поэтому определение (2) корректно.

Автомат называется приведённым автоматом, соответствующим автомату

Докажем, что у приведённого автомата все состояния отличимы друг от друга. Пусть Тогда для всех Отсюда по формуле (2) получаем, что при всех Следовательно, Отсюда следует, что Итак, у автомата неотличимыми являются только совпадающие друг с другом состояния.

Автомат и приведённый автомат работают одинаково: для любой входной последовательности последовательность на выходе автомата и автомата одна и та же: и т.д. (здесь начальное состояние). Решение типовых задач

Пример 1. Построить приведённый автомат для автомата, заданного следующей диаграммой Мура, изображенной на рис. 3.14.

Решение. Вычислим: , , , , . Следовательно, состояние отличимо от всех остальных. Мы получаем (пока) следующее разбиение множества на классы, т.е. непересекающиеся подмножества: (далее это разбиение будет измельчаться).

Далее вычисляем: Отсюда следует, что не может лежать в одном классе с или с или и т.д.

Разбиение, полученное ранее, измельчается до следующего:

Положим

Покажем, что это окончательное разбиение. Имеем:

поэтому

Аналогично получаем

и т.д., т.е. функция

“не разбивает” классы. Следовательно, классы

можно считать состояниями нового автомата. Это и есть приведённый автомат, его диаграмма Мура изображена на рисунке 3.15.

Пример 2. Построить приведённый автомат для автомата , заданного следующей таблицей 3.7:

Решение. Верхняя строка таблицы 11011 определяет разбиение нижняя строка - разбиение Их пересечение это разбиение Докажем, что состояния неотличимы друг от друга.