Эквивалентные состояния. Минимизация к.д.а

Определение. Две диаграммы Мура называются изоморфными, если они могут быть превращены одна в другую переобозначением вершин.

Определение. Два автомата называются изоморфными, если их диаграммы Мура изоморфны.

Рассмотрим два автомата и с одинаковыми входным и выходным алфавитами.

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

В частном случае, когда = , то речь идет о неотличимых состояниях одного автомата.

Определение. Автоматы и называются неотличимыми (эквивалентными) тогда и только тогда, когда для любого состояния найдется эквивалентное ему состояние и обратно.

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

Определение. Автомат А называется приведенным, если в нем нет эквивалентных (неразличимых) состояний.

Число состояний в приведенном автомате минимально. Для любого автомата существует эквивалентный ему приведенный автомат А. Процедура нахождения такого автомата называется минимизацией автомата .