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

Обратите внимание на строки , . Для возможности объединения состояний 3,4,5 необходимо, чтобы состояния 1,4 и 1,2 были совместимыми. Но, в силу определения совместимости состояний, переходы из 1,4 и 1,2 должны происходить также в совместимые состояния. Таким образом, получается цепь классов состояний, которые должны быть совместимыми.  

Если множество  классов совместимости включает в себя все состояния конечного автомата , то  покрывает множество состояний  и называется покрытием.

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

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

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

В примере было найдено множество максимальных классов совместимости: .

Если построить таблицу, строки которой соответствуют максимальным классам совместимости, то из нее можно выбрать различные покрытия множества состояний:

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

, , а множество  не входит ни в , ни в , ни в .

Обратите внимание, что состояние  покрывается только множеством  . Удалим из множества  состояние  и построим новую таблицу

Выберем покрытие . Строим последовательности состояний, порожденных этими множествами:

 à,;     à,;    à .

Условие замкнутости не нарушается, следовательно, минимальное замкнутое покрытие найдено.

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

Этап 4. Построение таблицы переходов – выходов минимального автомата.

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