Ангера-Полла
Для проектируемого частичного автомата, заданного таблицами переходов и выходов, первым шагом минимизации должно быть удаление недостижимых состояний, т.е. состояний, в которые автомат не может перейти из начального состояния ни при каких входных сигналах (исключение недопустимых состояний). Далее процесс минимизации частичных автоматов включает в себя три основных этапа: - нахождение всех максимальных классов совместимости; - нахождение минимального замкнутого покрытия; - получение по минимальному замкнутому покрытию минимизированного цифрового автомата. Автомат называется минимальным, если в нём нет совместимых состояний. Первый этап. Нахождение всех максимальных классов совместимости. Рассмотрим алгоритм получения совместимых пар с помощью треугольной таблицы, предложенный М. Поллом и С. Ангером на примере не полностью определенного автомата, заданного таблицами переходов и выходов, приведёнными в табл.4 и 5. По таблицам переходов и выходов автомата составляется треугольная таблица, столбцы и строки которой сопоставляются с состояниями автомата. Вид таблицы обусловлен рефлексивностью и симметричностью отношения совместимости состояний - она треугольная. Для упрощения записи в этой таблице вместо si будем писать i (символ состояния). Порядок вычерчивания треугольной матрицы. Количество строк матрицы m определяется из условия
m = i - 1, (1.3)
где i - количество состояний автомата. При заполнении строк исключается первое состояние автомата s1. Запись состояний осуществляется сверху вниз от s2 до sn (в нашем примере от s2 до s5). Количество столбцов матрицы n определяется из условия
n = i - 1. (1.4)
При заполнении столбцов матрицы исключается последнее состояние автомата sn. Запись состояний осуществляется слева на право от s1 до sn-1 (в нашем примере от s1 до s4). Треугольная таблица Ангера – Полла для рассматриваемого примера представлена таблицей 7. Таблица 7
Методика заполнения таблицы По таблице выходов (см. табл. 5) определяются несовместимые по выходу состояния. Несовместимыми по выходу состояниями являются состояния, у которых при воздействии на вход одного и того же сигналы xi Î X, выходные сигналы имеют разные значения yi Î Y и yj Î Y. При наличии таких состояний в треугольной матрице ставиться Х (крест). Для определения таких состояний осуществляется последовательное сравнение состояний s1 с s2, s1 с s3, s1 с s4 и т. д. Если при сравнении выходное слово не определено, то на основании допустимости входных сигналов, можно предположить, что выходные сигналы совпадают. Пример. Сравним состояния s1 с s2 по таблице выходов (см. табл. 5). x1 => y1 и y1 - выходные сигналы совпадают; x2 => y2 и y2 - выходные сигналы совпадают; x3 => -/- и y1 - выходные сигналы допустимо совпадают; x4 => y1 и -/- - выходные сигналы допустимо совпадают. На основании сравнения состояний можно сделать вывод о том, что состояния s1 и s2 совместимы по выходу. Далее сравниваем состояния s1 и s3 по выше приведенной методике. Не трудно видеть, что состояния s1 и s3 совместимы по выходу. При последовательном сравнении состояний по выходу обнаруживаем, что при сравнении состояний s2 и s5 выходные сигналы не совпадают. x1 => y1 и -/- - выходные сигналы допустимо совпадают; x2 => y2 и -/- - выходные сигналы допустимо совпадают; x3 => y1 и y2 - выходные сигналы не совпадают; x4 => -/- и -/- - выходные сигналы допустимо совпадают. При наличии хотя бы одного несовпадения, состояния считаются несовместимыми. Следовательно, состояния s2 и s5 несовместимы и в ячейке треугольной матрицы на пересечении состояний s2 и s5, ставиться Х (крест). При дальнейшем исследовании таблицы выходов видно, что больше несовместимых состояний по выходу нет. Дальнейшие исследования совместимости состояний осуществляются по таблице переходов (см. табл. 4). Определение абсолютно совместимых состояний без дополнительных условий. Абсолютно совместимыми состояниями называются состояния, у которых при воздействии одного и того же сигнала xi Î X осуществляется переход в одни и те же состояния si Î S. В этом случае в ячейке таблицы Ангера-Полла на пересечении рассматриваемых состояний ставится V (птичка). Если переход в состояние при воздействии входного сигнала не определен, то на основании допустимости входных слов считаем, что состояния, в которые переходит автомат, совпадают. Пример. Сравним состояния s1 с s2 по таблице переходов (см. табл. 4). x1 => s2 и s3 - состояния не совпадают; x2 => -/- и s5 - состояния допустимо совпадают; x3 => s3 и s2 - состояния не совпадают; x4 => s2 и -/- - состояния допустимо совпадают. При наличии хотя бы одного несовпадения, сравниваемые состояния не относятся к абсолютно совместимым состояниям без дополнительных условий. При сравнении состояний s1 и s3 нетрудно видеть, что и они не относятся к абсолютно совместимым состояниям. Вместе с тем, при сравнении состояний s3 и s5 видно, что при: x1 => s3 и -/- - состояния допустимо совпадают; x2 => s4 и -/- - состояния допустимо совпадают;
x3 => -/- и s1 - состояния допустимо совпадают; x4 => s5 и -/- - состояния допустимо совпадают. Состояний, которые не совпадают, нет. Следовательно, состояния s3 и s5 абсолютно совместимы без дополнительных условий. В треугольной матрице Ангера-Полла в ячейке на пересечении состояний s3 и s5 ставиться V (птичка). Из дальнейшего сравнения состояний видно, что больше абсолютно совместимых состояний нет. Определение условно совместимых состояний. С этой целью по таблице переходов проводим последовательное сравнение состояний, исключая несовместимые и абсолютно совместимые состояния. Пример. Сравним состояния s1 и s2 по таблице переходов (см. табл. 4). x1 => s2 и s3 - состояния не совпадают; x2 => -/- и s5 - состояния допустимо совпадают; x3 => s3 и s2 - состояния не совпадают; x4 => s2 и -/- - состояния допустимо совпадают. Из сравнения видно, что отличия состоят при воздействии входных сигналов x1 и x3. Следовательно, состояния s1 и s2 считаются совместимыми при условии, что совместимы состояния s2 и s3 (на основании симметричности s2 ~ s3 => s3 ~ s2). Поэтому в треугольной матрице Ангера-Полла в ячейке на пересечении состояний s1 и s2 записываем условия совместимости в виде 2.3. Сравниваем состояния s1 и s3. x1 => s2 и s3 - состояния не совпадают; x2 => -/- и s4 - состояния допустимо совпадают; x3 => s3 и -/- - состояния допустимо совпадают; x4 => s2 и s5 - состояния не совпадают. Из сравнения видно, что не совпадают состояния s2 и s3 при x1 и состояния s2 и s5 при x4. Следовательно, состояния s1 и s3 совместимы при условии, что совместимы состояния (s2 и s3) и (s2 и s5). В треугольной матрице в ячейке на пересечении состояний s1 и s3 записываем условия совместимости в виде 2.3 и 2.5. Продолжая дальнейшее сравнение состояний, заполняются все ячейки треугольной матрицы, вид которой представлен в таблице 8. Дальнейшее определение совместимых и несовместимых состояний осуществляется из анализа таблицы 8 путем последовательного просмотра столбцов. Шаг 1. Находятся абсолютно несовместимые состояния. В данном случае это состояния (s2 и s5). Просматривая столбцы треугольной матрицы и в тех ячейках, где имеются сочетания состояний s2 и s5 (2.5) ставиться Х (крест). Таблица 8
Так как состояние (s 2 и s 5) несовместимы, следовательно, несовместимы состояния (s 1 и s 3) по условию совместимости. В ячейке на пересечении состояний s 1 и s 3 ставится Х (крест).В результате получим таблицу 9. Шаг 2. Просматривая столбцы треугольной матрицы таблицы 9, там, где в ячейках есть сочетание состояний (s 1 и s 3) ставиться Х (крест). На основании условий совместимости несовместимыми состояниями являются состояния (s 1 и s 5). В результате получим табл. 10. Таблица 9
Шаг 3. Просматривая таблицу 10, там, где в ячейках есть сочетание состояний (s1 и s5) ставиться Х (крест). Несовместимыми состояниями будут состояния (s2 и s4). Этот просмотр проводится для всех клеток, отмеченных крестом, и заканчивается тогда, когда таких клеток не остаётся. В этом случае клетки без крестов соответствуют совместимым парам состояний, а клетки с крестами – несовместимым. Таблица 10
В результате исключения несовместимых состояний получим треугольную матрицу совместимых состояний. После сравнения всех ячеек треугольной матрицы (см. табл. 10) рассматриваемого примера, получаем следующий результат: пары состояний (1, 2), (1, 4) совместимы при условии совместимости пары состояний (2, 3); пары состояний (2, 3) совместимы при условии совместимости пары состояний (4, 5); пары состояний (4, 5) совместимы при условии совместимости пары состояний (1, 2); пары состояний (3, 4) совместимы при условии совместимости пары состояний (1, 4); пары состояний (3, 5) абсолютно совместимы. Пары состояний (1, 3), (1, 5), (2, 4), (2, 5) не совместимы, так как в ячейках на их пересечениях стоят Х (кресты). Не трудно видеть, что совместимость одних пар состояний определяется совместимостью других пар. Причём, имеются состояния, которые входят в разные пары совместимости. Отсюда можно сделать вывод, что совместимыми могут быть не только пары состояний, но и большее количество состояний. Будем говорить, что множество полученных совместимых состояний В, принадлежащих алфавиту состояний цифрового автомата А (В Î А) совместимо с состоянием sm (sm ~ В), принадлежащее алфавиту состояний цифрового автомата А (sm Î A), если состояние sm совместимо с состоянием sn (sm ~ sn) для любого sn, принадлежащего множеству В (sn Î В). С целью отыскания нескольких совместимых состояний необходимо определить максимальные классы совместимости.
|
