Минимизация абстрактного конечного автомата

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 23:19, 7 июня 2016.

Введение

Минимизация абстрактного конечного автомата - первый этап задачи структурного синтеза конечного автомата. В данной статье рассмотрены примеры минимизации автоматов Мили и Мура.

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

Законы функционирования:

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

Особенностью автомата Мили является то, что функция выходов является двухаргументной и символ в выходном канале y(t) обнаруживается только при наличии символа во входном канале x(t). Функциональная схема не отличается от схемы абстрактного автомата.

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

Законы функционирования:

Автомат Мура является частным случаем автомата Мили.

Минимизация автомата Мура

Вариант 1

Рис. 1. Автомат Мура
Рис. 2. Минимизированный автомат Мура

На рис. 1 изображен граф автомата Мура, который необходимо минимизировать.

Составим таблицу переходов автомата.

a b c d

Для упрощения автомата в первую очередь необходимо выделить эквивалентные состояния. Колдуэлл сформулировал 2 условия эквивалентности автоматов.

Условия эквивалентности Колдуэлла:

  1. Необходимое условие: внутренние состояния и называются эквивалентными, если при подаче произвольной входной последовательности с начальными состояниями и образуются одинаковые выходные последовательности.
  2. Достаточное условие: если две одинаковые строки выходят в следующее состояние, то эти состояния эквивалентны.

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

Эквивалентных состояний нет. Произведём замену .

a b c d

Получаются следующие классы эквивалентности:

Автомат, изображенный на рис. 2, является минимальным.

Вариант 2

На рис. 3 представлен автомат Мура:

Рис. 3. Автомат Мура

Составим таблицу переходов/выходов:

Разобьем на классы эквивалентности и получаем следующее:

Сделаем замену:



Составим новую таблицу переходов/выходов:

В итоге получаем минимизированный автомат Мура (рис. 4).

Рис. 4. Минимизированный автомат Мура.

Минимизация автомата Мили

Вариант 1

Рис. 5. Автомат Мили
Рис. 6. Минимизированный автомат Мили

На рис. 5 изображен граф автомата Мили, который необходимо минимизировать.

Составим таблицу переходов автомата:

a b c d

Состояния и эквивалентны. Классы эквивалентости:

Автомат, изображенный на рис. 6, является минимальным.






Вариант 2

На рис. 7 изображен автомат Мили.

Рис. 7. Автомат Мили

Составим таблицу переходов/выходов:

Разбиваем на классы эквивалентности и получаем следующее:

Сделаем замену:

Составим новую таблицу переходов/выходов:

В итоге получаем минимизированный автомат Мили (рис. 8).

Рис. 8. Минимизированный автомат Мили