Проектирование минимального частично определенного автомата

Введение

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

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

Проектирование минимального частично определенного автомата

Необходимо отметить, что если у автомата Мили функция переходов d(а, х) на заданной паре (а, х) не определена, то это должно означать неопределенность значения на этой паре и функции выходов l(а, х). А поскольку эта пара значений аргументов считается запрещенной для функции переходов, то теряет смысл задание на этой паре какого-либо определенного значения функции выходов. Даже когда выполняется описание предполагаемого последнего шага работы автомата, то он обязан завершиться в состоянии а0, чтобы был сформирован автомат многократного действия, подготовленный к новому циклу работы.

Не имеет смысла и противоположный вариант, то есть, функция переходов является определённой, а функция выходов не определена. Единственным исключением является вариант, когда рассматривается выход автомата Мура в начальном состоянии в момент t = 0. Но и в этом варианте лучше задавать функции выхода значение «е», то есть, пустую выходную букву. Это замечание позволяет не рассматривать указанные надуманные ситуации, что часто выполняется в специальной литературе по теории автоматов.

Рассмотрим алгоритм минимизации частичных автоматов, который основан на выявлении совместимых состояний (алгоритм Пола и Ангера). Следует различать два типа совместимости состояний, а именно:

1. Безусловная совместимость.
2. Условная совместимость.

В таблице ниже указаны примеры безусловной совместимости состояний автомата Мили.

Рисунок 1. Таблица. Автор24 — интернет-биржа студенческих работ

Состояния а0 и а1 являются безусловно совместимыми. Если выполнить объединение этих двух строк в одну и вместо а1 всюду писать а0, то это не должно приводить к противоречию. Помимо этого, безусловно совместимыми являются состояния а2, а3 и а4. Содержимое клеток в соответствующих строках или просто одно и тоже, или у одной из сравниваемых строк не является определённым. В данном случае совместимы сразу три из всего набора состояний, и они могут быть заменены каким-то одним.

Множества совместимых состояний именуются группами совместимости. Но считать их классами совместимости нельзя, поскольку в отличие от классов группы совместимости могут пересекаться. Например, в таблице, приведённой выше, совместимыми являются а1 и а3, принадлежащие разным выделенным ранее группам. Условная совместимость обладает цепным характером. Необходимым условием совместимости одних состояний считается совместимость некоторых других состояний. Пример условной совместимости приведён в таблице ниже.

Рисунок 2. Таблица. Автор24 — интернет-биржа студенческих работ

Строки данной таблицы нигде не имеют полных совпадений, однако состояния а0 и а3 являются безусловно совместимыми, а состояния а1 и а2 могут оказаться совместимыми, в случае обеспечения совместимости а0 и а3.

Цепная зависимость совместимостей одних состояний от совместимости других может быть показана в графическом формате. Для таблицы, приведённой выше, граф условий совместимости может выглядеть следующим образом (а1 и а2 являются совместимыми, если совмещаются а0 и а3):

Рисунок 3. Граф. Автор24 — интернет-биржа студенческих работ

Пара (а0, а3) может считаться порожденной от (а1, а2). Выполнить объединение состояний первой пары в одно можно лишь после того, как будут объединены состояний в порожденной паре.

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

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

1. Определение всех максимальных классов совместимости.
2. Определение минимального замкнутого покрытия.
3. Получение по минимальному замкнутому покрытию автомата.