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

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

Помечаем клетку для несовместимой пары 1,3 вторым символом  и ищем клетки, где встречается пара 1,3 и помечаем их крестом. В примере это клетка для пары

Помечаем клетку для несовместимой пары 1,5 вторым символом  и ищем клетки, где встречается пара 1,5 и помечаем их крестом. В примере это клетка для пары :

Помечаем клетку для несовместимой пары 2,4 вторым символом  и ищем клетки, где встречается пара 2,4. В примере таких клеток нет. Поскольку в таблице не осталось не просмотренных несовместимых состояний (просмотренная клеточка несовместимых состояний помечена ), то поиск совместимых пар закончен. Клетки без  соответствуют совместимым состояниям, а с  - несовместимым состояниям:

1~2,  1~4,  2~3,  3~4, 3~5,  4~5;

1~3,  1~5,  2~4,  2~5.

Этап 2. Вычисление максимальных классов совместимости.

Шаг 1. Берем все множество состояний автомата {1,2,3,4,5}. Рассматриваем первый столбец треугольной таблицы, соответствующий состоянию 1и находим в нем состояния 3 и 5 несовместимые с 1 (они помечены символами ). Т.к. состояние 1 несовместимо с состояниями 3 и 5, то они не могут находится в одном множестве совместимых состояний:

                                         {1,2,3,4,5}

{1,2,4}          {2,3,4,5}

Шаг 2. Рассматриваем второй столбец треугольной матрицы, соответствующий состоянию 2 и находим состояния 4 и 5 несовместимые с состоянием 2. Разбиваем ранее полученные множества на подмножества таким образом, чтобы они не содержали несовместимых состояний:

{1,2,4}                     {2,3,4,5}

{1,2}       {1,4}             {2,3}    {3,4,5}

Поскольку столбцы, соответствующие состояниям 3 и 4 не содержат , то получены максимальные классы совместимости. Каждое множество содержит только попарно совместимые состояния.

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

Этап 3. Получение минимального замкнутого покрытия.

Посмотрим, что получается при замене состояний из класса совместимости одним состоянием. Заменим столбцы состояний 3,4,5 одним столбцом . В позиции для выходного сигнала в строке этого столбца ставится прочерк, если во всех объединяемых столбцах в этой строке стоит прочерк, иначе в эту строку вписывается выходной сигнал стоящий в объединяемых столбцах на данной строке.