Основной алгоритм минимизации абстрактного автомата Мура

минимизации абстрактного автомата Мили:

Для табличного описания процедура минимизации цифровых автоматов алгоритмизирована и выполняется в несколько шагов.

Шаг 1.Распространение неопределённости таблицы выходов на таблицу переходов. Если для некоторой пары (am, zf)выходной сигнал автомата не определён, то для этой пары не определяется и функция перехода, так как не определено допустимое слово, осуществляющее переход из этого состояния.

Шаг 2.Исключение недостижимых состояний. Если в автомате имеется состояние (но только не начальное), в которое он не может попасть под воздействием любого допустимого входного слова, то такое состояние называется недостижимым. Недостижимые состояния исключаются из описания абстрактного автомата без изменения индуцируемого автоматом отображения. Автомат, все состояния которого достижимы, является связным автоматом. Выполнение первых двух шагов минимизации иллюстрируется на примере автомата Мили S9.

Шаг 3.Нахождение совместимых состояний автомата.

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

При выполнении операции расщепления классов специальный символ неопределённости может быть заменён номером (индексом) любого класса. Если операцию расщепления i– классов применить последовательно, начиная с 1 – класса, то через конечное число шагов процесс расщепления закончится. Нерасщепляемые далее классы образуют классы совместимых состояний. Иногда отметки состояний разных классов совпадают, но объединять такие состояния в один класс (i+1)– совместимости совершенно недопустимо.

Отыскание классов совместимых состояний рассмотрим для примера автомата Мили S10, описываемого совмещённой табл. 31 переходов и выходов. Процедуру расщепления классов для нахождения классов конечной совместимости удобно проводить с использованием таблиц (рис.34).

Задачей минимизации методом расщепления классов совместимости является получение как можно меньшего количества, как можно большей ёмкости классов конечной совместимости. Поэтому состояние 8 (a8) первоначально отнесённое к двум классам двоичной совместимости из–за неопределённой первой отметки окончательно должно быть отнесено ко второму классу. Классы двоичной совместимости далее не расщепляются.

Таким образом, доопределяются неопределённые переходы исходного автомата. Нормализованный автомат является эквивалентным любому из минимизированных автоматов и не имеет, как минимум, ни одной пары совместимых состояний. В соответствии с изложенной методикой минимизации получаются либо полностью определённые, либо частичные нормализованные автоматы. У полностью определённых автоматов классы конечной совместимости не пересекаются, поэтому нормализованный автомат является единственным и процесс минимизации этим заканчивается. В случае получения частичного автомата классы i– совместимости пересекаются. Это приводит к тому, что нормализованный автомат может описываться конечным количеством вариантов таблиц или графов. В случае частичных автоматов часто отказываются от достижения абсолютной минимизации и ограничиваются нахождением нормализованного автомата и его эвристическим доопределением.

Таким образом, основной алгоритм минимизации автомата Мили состоит из сле-

дующих шагов:

1. Распространение неопределённости выходов на переходы автомата.

2. Исключение недостижимых состояний.

3. Определение классов совместимости и построение нормализованного автомата.

4. Минимизация нормализованного автомата.

Для полностью определённого цифрового автомата отсутствует последний шаг алгоритма.

Для сложных автоматов возможно изменение очерёдности выполнения шага 2 и шага 3 этого алгоритма, поскольку для минимизированного нормализованного автомата определение недостижимых состояний требует меньших затрат труда и времени. Совмещённая таблица переходов и выходов нормализованного минимизированного автомата Мили S10представлена в табл. 32, а его граф – на рис. 35.

Дата добавления: 2015-07-26; просмотров: 789; Нарушение авторских прав

Мы поможем в написании ваших работ!