Теория множеств. Тождества алгебры множеств. Основные понятия теории графов. Методы задания конечных автоматов. Синтез функциональной схемы конечного автомата, страница 34

Получено разбиение на множества одноэквивалентных состояний и .

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

После заполнения таблица будет иметь вид:

Выделяя одинаковые столбцы для состояний, принадлежащих одному и тому же множеству, получаем разбиение , , , , . Разбиение  определяет множества двухэквивалентных состояний.

Строим таблицу  для поиска трех-эквивалентных состояний:

. , , , , .

Строим таблицу для поиска четырех-эквивалентных состояний:

. , , , , .

Разбиение , следовательно, найдены эквивалентные состояния. Оставим в каждом множестве эквивалентных состояний по одному состоянию. Для этого удалим из множества  состояние , и состояния  из множества . Вычеркиваем столбцы, соответствующие удаленным состояниям из таблицы переходов – выходов:

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

При минимизации автоматов Мура одинаково отмеченные состояния считаются 0 – эквивалентными, а поиск эквивалентных состояний начинается с поиска разбиения .

Пример.