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

Минимизация абстрактных цифровых автоматов

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

Два полностью определённых автомата называются эквивалентными, если они индуцируют (производят) одно и то же отображение множества входных слов во множество выходных слов.

Частичный цифровой автомат индуцирует лишь частичное отображение множества входных с лов в выходные слова.

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

Полностью определённый автомат является частным случаем частичного автомата.

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

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

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

Выполнение первых двух шагов минимизации иллюстрируется на примере автомата Мили S₉.

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

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

Состояния называются i - совместимыми для i = 1, 2,..., если результат применения к этим состояниям любого слова длины i будет одинаковым. Классы совместимых состояний могут быть найдены непосредственно по таблице выходов. В один и тот же 1 - класс зачисляются состояния, обозначающие совпадающие (с точностью до неопределённых выходных сигналов) столбцы таблицы выходов. Классы (i+1) - совместимости получаются из классов i - совместимости путём их расщепления на классы (i+1) - совместимости. Для этого у каждого состояния, принадлежащего j - классу i - совместимости C_j(i), номера классов (индексы), в которые автомат переходит под воздействием каждой входной буквы. Если номер класса не определён, то ставится специальный символ, например, прочерк. Индексы классов, в которые переходит автомат под действием входного сигнала образуют отметку. Множество состояний с одинаковыми отметками в классе C_j(i) образуют классы (i+1) - совместимости. При выполнении операции расщепления классов специальный символ неопределённости может быть заменён номером (индексом) любого класса. Если операцию расщепления i - классов применить последовательно, начиная с 1 - класса, то через конечное число шагов процесс расщепления закончится. Нерасщепляемые далее классы образуют классы совместимых состояний. Иногда отметки состояний разных классов совпадают, но объединять такие состояния в один класс (i+1) - совместимости совершенно недопустимо.

Отыскание классов совместимых состояний рассмотрим для примера автомата Мили S₁₀, описываемого совмещённой таблицей 30 переходов и выходов.

Процедуру расщепления классов для нахождения классов конечной совместимости удобно проводить с использованием таблиц (рис.34).

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

Всё множество совместимых состояний определяет некоторое множество минимизированных автоматов. Все они могут быть представлены нормализованным автоматом, в котором вместо состояний используются классы конечной совместимости. Для получения нормализованного автомата в процессе минимизации нужно строго следить за тем, чтобы начальное состояние всегда находилось в классе с индексом 1.

При построении нормализованного автомата переход d = (С_i, z_j) считается неопределённым, если для всех состояний этого класса не определены переходы в другое состояние. Если хотя бы для одного состояния класса переход определён, то в клетку таблицы нормализованного автомата заносится индекс класса, в который переходит цифровой автомат из этого состояния. Таким образом доопределяются неопределённые переходы исходного автомата. Нормализованный автомат является эквивалентным любому из минимизированных автоматов и не имеет, как минимум, ни одной пары совместимых состояний. В соответствии с изложенной методикой минимизации получаются либо полностью определённые, либо частичные нормализованные автоматы. У полностью определённых автоматов класс конечной совместимости не пересекаются, поэтому нормализованный автомат является единственным и процесс минимизации этим заканчивается. В случае получения частичного автомата классы i - совместимости пересекаются. Это приводит к тому, что нормализованный автомат может описываться конечным количеством вариантов таблиц или графов. В случае частичных автоматов часто отказываются от достижения абсолютной минимизации и ограничиваются нахождением нормализованного автомата и его эвристическим доопределением.

Таким образом, основной алгоритм минимизации автомата Мили состоит из следующих шагов:

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

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

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

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

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

Для сложных автоматов возможно изменение очерёдности выполнения шага 2 и шага 3 этого алгоритма, поскольку для минимизированного нормализованного автомата определение недостижимых состояний требует меньших затрат труда и времени.

Совмещённая таблица переходов и выходов нормализованного минимизированного автомата Мили S₁₀ представлена в таблице 31, а его граф - на рис. 35.

Более подробно рассмотрим применение методики минимизации автоматов Мили на примере полностью определённого автомата S₁₁.

Расщепление на классы пятиричной совместимости является конечным, так как метки в пределах классов для всех состояний класса одинаковы и, следовательно, дальнейшее расщепление классов невозможно. Метки состояний соответствуют переходам автомата. По этим меткам определяется, что классы G₂ и G₇ являются недостижимыми состояниями для нормализованного автомата.

Граф минимизированного нормализованного автомата Мили S₁₂ представлен на рис.36.

После исключения недостижимых состояний получен минимальный нормализованный автомат Мили S₁₃, представленный совмещённой таблицей 34 переходов и выходов.

Дата добавления: 2014-01-07