Определение максимальных классов совместимости
Рассмотрим способ нахождения максимальных классов совместимости из совместимых пар. Алгоритм нахождения всех максимальных классов совместимости сводится к следующему. Начинаем составление списка Ф классов совместимости с совместимых пар в крайнем правом столбце таблицы 10, имеющем, по крайней мере, одну клетку без крестов. Если в последнем столбце таблицы Ангера-Полла состояния не совместимы, переходим к предыдущему столбцу. Продвигаясь влево, записываем для каждого n-го столбца множество состояний Si ~ sj, т.е. множество всех состояний, соответствующих клеткам без крестов в n-м столбце таблицы и сравниваем их попарно с полученным списком максимальных множеств состояний. Рассмотрим последний столбец таблицы 10 (состояние s4). В данном столбце имеется два совместимых состояния 4 и 5. Следовательно, первым множеством Ф будет Ф1 = {4, 5}. Рассматривая столбец слева от последнего (состояние s3) видим, что в этом столбце две пары совместимых состояния 3 и 4, а также 3 и 5. На основании свойства отсутствия транзитивности следует что если s4 ~ s3 & s3 ~ s5 Þ s4 ~ s5. В нашем примере {3}~{4, 5} (в третьем столбце таблицы нет крестов в строках 4 и 5). Каждое множество Si ({3} и {4, 5}) пересекаем с каждым членом текущего списка Ф1. В рассматриваемом примере при рассмотрении пересечения множество {4, 5} и список Ф1 содержит единственный элемент {4, 5}, следовательно {4, 5}~{4, 5} = {4, 5}. Если пересечение содержит более одного состояния, то добавляем в список состояние {3} с результатом пересечения {3}~{4, 5} = {3, 4, 5}. Следовательно новый список Ф2 будет включать в себя два множества совместимых состояний Ф2= {{4, 5}, {3, 4, 5}}. Далее проводится минимизация полученного множества Ф2 - устранение всех повторений множеств в текущем списке и удаление всех множеств, содержащихся в других множествах списка. Не трудно видеть, что множество {4, 5} полностью входит во множество {3, 4, 5}, которое является максимальным классом совместимости, и поглощается ею. Следовательно, совместимыми будут состояния s3, s4 и s5, ({3}~{4, 5}), а результирующий список классов совместимости будет иметь вид Ф2 = {{3, 4, 5}}. Далее рассматриваем столбец состояния (s2). В нем только одна пара совместимых состояний s2 и s3. Следовательно, его список будет иметь вид Ф3 = {{2, 3}}. Сравниваем его с предыдущим списком. Нетрудно видеть, что по отношению друг к другу они будут относиться к максимальным классам совместимости, т. к. во втором списке Ф2 классов совместимости отсутствует состояние s2. Отсюда новым списком максимальных классов совместимости будет Ф4 = {{3, 4, 5}, {2, 3}}. При рассмотрении столбца состояния s1 каждые совместимые состояния {1}~{2, 4} сравниваем с полученным списком. После сравнения видно, что оба множества по отношению к списку Ф4 являются максимальными, так как ни одно из них полностью не входят ни в одно из множеств класса совместимости Ф4. Следовательно, разобьем их на множества попарно совместимых состояния {1, 2} и {1, 4}. Списки совместимых состояний s1 и s4, а также s1 и s2 по отношению к предыдущему списку будут максимальны. Новым списком максимальных классов совместимости будет множество
Ф = {{3, 4, 5}, {2, 3}, {1, 2}, {1, 4}}. (1.5)
Очевидно, что результирующий список множеств классов совместимости Ф является списком всех максимальных классов совместимости. Для удобства синтеза цифрового автомата переставим множества совместимых классов в порядке следования состояний автомата. Для рассмотренного автомата, множество всех классов совместимости будет иметь вид
Ф = {{1, 2}, {1, 4}, {2, 3}, {3, 4, 5}}. (1.6)
Второй этап - определение минимального замкнутого покрытия - достаточно сложная задача, связана с перебором возможных замкнутых покрытий. Алгоритм получения минимального замкнутого покрытия достаточно подробно описан в [3] здесь не рассматривается. В качестве исходного замкнутого покрытия будим рассматривать множество максимальных классов совместимости Ф = {{1, 2}, {1, 4}, {2, 3}, {3, 4, 5}}. Третий этап. Процедура получения минимизированного автомата В = (X', Y', S', d', l'), представляемого найденным для исходного автомата А (1.1) замкнутым покрытием Ф, достаточно проста. Каждому классу совместимости ciÎ Ф ставится в соответствие состояние si' нового минимального автомата В. Для каждого класса совместимости ci Î Ф (1.6) и каждого входного сигнала xi Î X вычисляется множество следующих за ci состояний минимального автомата В {bi = d(ci, xi)}. Применим эту процедуру к рассматриваемому примеру. В качестве исходного замкнутого покрытия, как уже отмечалось выше, возьмем множество максимальных классов совместимости (1.6). Поставим ему в соответствие множество состояний нового автомата В ={b1, b2, b3, b4}. Классу совместимости {1, 2} ставим в соответствие состояние b1 нового минимального автомата, классу совместимости {1, 4} состояние b2, классу совместимости {2, 3} состояние b3 и классу совместимости {3, 4, 5} состояние b4. По таблице переходов исходного автомата (см. табл. 4) составляем таблицу перехода минимизированного автомата. С этой целью по табл. 4 одновременно рассматриваем столбцы с состояниями, соответствующие классам совместимости. За классом {1, 2} (столбцы 1 и 2 табл. 4), что соответствует состоянию b1 автомата В по входу x 1 следует класс {2, 3}, что соответствует состоянию b3 автомата В. По входу x 2 - класс {5} (b4), по входу x 3 - класс {2, 3} (b3), по входу x 4 - {2} (b1 – так как он стоит первым во множестве Ф). Следовательно, в минимизированном автомате, получающимся в результате совмещения состояний {1, 2}, должны быть совместимы состояния {1, 2}, {2, 3}, {5}, {2, 3}, {2}, что в нашем случае верно. В результате рассмотрения класса совместимости {1, 2} исходного автомата А получаем следующие значения функций переходов и выходов минимизированного автомата В: функции переходов для состояния b1 при воздействии входных сигналов х 1, х 2, х 3 и х 4: d'(b1, x 1) = s2 и s3 – что соответствует b3 или d'(b1, x 1) = b3; d'(b1, x 2) = s5 – что соответствует b4 или d'(b1, x 2) = b4; d'(b1, x 3) = s2 и s3 – что соответствует b3 или d'(b1, x 3) = b3; d'(b1, x 4) = s2 – что соответствует b1 или d'(b1, x 4) = b1. Функции выходов для состояния b1 при воздействии входных сигналов х 1, х 2, х 3 и х 4 определяются как: l' (b1, x 1) = y1и y1 – что соответствует l' (b1, x 1) = y1; l' (b1, x 2) = y2 – что соответствует l' (b1, x 2) = y2; l' (b1, x 3) = y1 – что соответствует l' (b1, x 3) = y1; l' (b1, x 4) = y1 и y1 – что соответствует l' (b1, x 3) = y1. Аналогичную процедуру проводим для остальных классов совместимости. Методика составления таблиц переходов и выходов минимизированного автомата. Вычерчиваем таблицу состояний минимизированного автомата. В рассматриваемом примере это составляет пять строк и пять столбцов, в соответствии с методикой изложенной выше (см. п.п. 1.1). Рассматриваем класс совместимости {1, 2} соответствующий состоянию b1 минимизированного автомата. По входному сигналу x 1 исходный автомат переходит в состояния {2, 3} (см. табл. 4). Это соответствует состоянию b3 минимизированного автомата. В ячейке на пересечении столбца b1 и строки x 1 таблицы переходов нового автомата ставиться состояние b3. По входному сигналу x 2 исходный автомат переходит в состояние {5}. Это соответствует состоянию b4 минимизированного автомата. В ячейке на пересечении столбца b1 и строки x 2 таблицы переходов нового автомата ставиться состояние b4. По входному сигналу x 3 исходный автомат переходит в состояния {3, 2}. Это соответствует состоянию b3 минимизированного автомата. В ячейке на пересечении столбца b1 и строки x 3 таблицы переходов нового автомата ставиться состояние b3. По входному сигналу x 4 исходный автомат переходит в состояние {2}. Это соответствует состоянию b1 минимизированного автомата. В ячейке на пересечении столбца b1 и строки x 4 таблицы переходов нового автомата ставиться состояние b1. Далее рассматриваем класс совместимости {1, 4} соответствующий состоянию b2 минимизированного автомата. По входному сигналу x 1 исходный автомат переходит в состояние {2}, что соответствует состоянию b1 минимизированного автомата. В ячейке на пересечении столбца b2 и строки x 1 таблицы переходов нового автомата ставиться состояние b1. По входному сигналу x 2 исходный автомат переходит в состояние {1}, что соответствует состоянию b1 минимизированного автомата. В ячейке на пересечении столбца b2 и строки x 2 таблицы переходов нового автомата ставиться состояние b1. По входному сигналу x 3 исходный автомат переходит в состояния {3, 2}, что соответствует состоянию b3 минимизированного автомата. В ячейке на пересечении столбца b2 и строки x 3 таблицы переходов нового автомата ставиться состояние b3. По входному сигналу x 4 исходный автомат переходит в состояние {2}. Это соответствует состоянию b1 минимизированного автомата. В ячейке на пересечении столбца b2 и строки x 4 таблицы переходов нового автомата ставиться состояние b1. Последовательно рассматривая оставшиеся классы совместимости, составляем таблицу переходов минимизированного автомата, представленной таблицей 11. Таблица 11
Таблица выходов минимизированного автомата составляется в соответствии с таблицей выхода исходного цифрового автомата А (см. табл. 5). Рассматриваем класс совместимости {1, 2} соответствующий состоянию b1 минимизированного автомата. По входному сигналу x 1 на выходе исходного автомата в этих состояниях будет выходной сигнал y1 (см. табл. 5). В ячейке на пересечении столбца b1 и строки x 1 таблицы выходов минимизированного автомата ставиться выходной сигнал y1. По входному сигналу x 2 на выходе исходного автомата будет сигнал y2. В ячейке на пересечении столбца b1 и строки x 2 таблицы выходов минимизированного автомата ставиться выходной сигнал y2. По входному сигналу x 3 на выходе исходного автомата будет сигнал y1. В ячейке на пересечении столбца b1 и строки x 3 таблицы выходов минимизированного автомата ставиться выходной сигнал y1. По входному сигналу x 4 на выходе исходного автомата будет сигнал y1. В ячейке на пересечении столбца b1 и строки x 4 таблицы выходов минимизированного автомата ставиться выходной сигнал y1.
Последовательно рассматривая оставшиеся классы совместимости, составляем таблицу выходов минимизированного автомата В, представленной таблицей 12. Таблица 12
|
