Алгоритм Ангера-Полла

Частично-определенные автоматы.

A'''2~a2

A''2~a2 a''3~a3

A0~a0 a'1~a1 a'2~a2 a'3~a3

A3~a'3

A2~a'2

A1~a'1

покажем обратное утверждение

Определение:

Частично-определeнный (неполностью-определeнный) автомат - это автомат, у которого функции "l" и/или "d" определены не полностью, значит, у него входные слова могут быть допустимыми и не допустимыми.

Определение:

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

Свойства совместимости состояний:

a_m ~ a_n,

a_m ~ a_n => a_n ~ a_m,

a_m ~ a_k & a_n ~ a_k!=> a_m ~ a_n (т.е. нет транзитивности).

Утверждение: Два состояния a_m и a_n совместимы, то есть a_m ~ a_n если:

d(a_m,z_i)=d(a_n,z_i) для любого z_i из Z, (условие совместимости по переходу)

l(a_m,z_i)=l(a_n,z_i) для любого z_i из Z. (условие совместимости по выходу)

Определение

Классом совместимости состояний C называют множество состояний, все элементы которого попарно совместимы друг с другом.

Класс совместимости максимален, если он не содержится полностью в другом. Классом совместимости также является класс B=d(C,z_i), если С - класс совместимости.

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

Нахождение всех максимальных классов совместимости.

Нахождение минимального замкнутого покрытия.

Получение по минимальному замкнутому покрытию нового автомата.

Первый этап.

Рассмотрим алгоритм получения совместимых пар с помощью треугольной таблицы, предложенной М.Поллом и С. Ангером. Рассматривать будем на примере автомата, заданного следующими таблицами переходов и выходов:

d a1 a2 a3 a4 a5 z1 a2 a3 a3 -- -- z2 -- a5 a4 a1 -- z3 a3 a2 -- a2 a1 z4 a2 -- a5 -- --

l a1 a2 a3 a4 a5 z1 w1 w1 w1 -- -- z2 w2 w2 w2 w2 -- z3 -- w1 -- -- w2 z4 w1 -- w1 -- --

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

В треугольной таблице на пересечении строки m и столбца s ставятся:

Х (крест), если состояния a_m и a_s несовместимы по выходу, например а₂ и а₅ (в таблице выходов в строке z₃ в столбцах a₂ и а₅ стоят разные выходные сигналы - w₁ и w₂ соответственно).

множество всех пар состояний, следующих за парой (a_m, a_s) и отличных от неё - все те пары, совместимость которых необходима для совместимости пары (a_m, a_s). Например, для совместимости (а₁, а₃) необходима совместимость (а₂, а₃) и (а₂, а₅), так как (а₂, а₃) и (а₂, а₅) следуют за множеством (а₁, а₃) по входам z₁ и z₄ соответственно.

V (птичка), если за (а_m, а_s) не следуют пары, отличные от (а_m, а_s), т.е. пара (а_m, а_s) совместима без дополнительных условий, налагаемых на совместимость других пар. В нашем примере это пара (а₃, а₅).

Для нахождения несовместимых пар состояний (и, следовательно, совместимых пар тоже) треугольная таблица просматривается по столбцам. Находится первая клетка, отмеченная крестом. Пусть это будет клетка (i, j) - в нашем примере (2, 5). Тогда во всех клетках, где есть пара (i, j), ставится крест, а уже рассмотренная клетка (i, j) отмечается вторым крестом. Эта процедура проводится для всех клеток (включая новые), отмеченных одним крестом, и заканчивается, когда таких клеток не остается. Очевидно, что в этом случае клетки без крестов соответствуют совместимым парам состояний, а клетки с крестами - несовместимы. Так, после применения этой процедуры к треугольной таблице нашего примера, получаем следующий результат: "

a2 2.3       a3 2.3 2.5 4.5     a4 2.3 1.5 1.4   a5 1.3 X V 1.2   a1 a2 a3 a4

==>

a2 2.3       a3 2.3X 2.5X 4.5     a4 2.3 1.5XX 1.4   a5 1.3XX XX V 1.2   a1 a2 a3 a4

Из этой таблицы видно, что следующие пары состояний совместимы: (1, 2), (1, 4), (2, 3), (3, 4), (3, 5), (4, 5). А пары состояний (1, 3), (1, 5), (2, 4), (2, 5) не совместимы. Теперь рассмотрим способ нахождения максимальных классов совместимости из совместимых пар. Будем говорить, что множество состояний В (В Í А) совместимо с некоторым состоянием a_m Î A (обозначение a_m~В), если и только если a_m ~ a_s для любого a_s Î В.

Алгоритм нахождения всех максимальных классов совместимости сводится к следующему:

Начинаем составление списка Ф классов совместимости с совместимых пар в крайнем правом столбце треугольной таблицы, имеющем по крайней мере одну клетку без крестов. В примере Ф = {{4, 5}}.

Продвигаясь влево, выписываем для каждого i -го столбца множество состояний А_i ~ a_i, т.е. множество всех состояний, соответсвующих клеткам без крестов в i -ом столбце таблицы. В нашем примере 3~{4,5} (в третьем столбце таблицы нет крестов в строках 4 и 5).

Каждое А_i пересекаем с каждым членом текущего списка Ф. У нас А₃ = {4, 5} и список Ф также содержит единственный элемент {4, 5}:

{4,5}Ç{4,5}={4,5}.

Если такое пересечение содержит более одного состояния, то добавляем в список объединение {a_i} с результатом пересечения:

{3}È{4,5}={3,4,5}; Ф={{4,5},{3,4,5}}.

Далее проводится максимизация полученного множества Ф - устранение всех повторений множеств в текущем списке и удаление всех множеств, содержащихся в других множествах списка:

Ф={{3,4,5}}.

Добавляем в список все пары, состоящие из a_i и различных состояний из А_i, и не являющиеся подмножествами других членов списка Ф (при i = 3 таких добавлений нет).

Приведём полностью результат применения второго шага ко всем столбцам:

Ф={{4,5}};

{3}~{4,5}, Ф={{3,4,5}};

{2}~{3}, Ф={{3,4,5},{2,3}};

{1}~{2,4}, Ф={{3,4,5},{2,3},{1,2},{1,4}};

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

Очевидно, что результирующий список Ф является списком всех максимальных классов совместимости. Таким образом, для автомата, рассмотренного нами, множество всех классов совместимости

Ф={{3,4,5},{2,3},{1,2},{1,4}}.

Второй этап - нахождение минимального замкнутого покрытия - достаточно сложная задача, не представляющая для нас особого интереса. Подробное описание этого алгоритма можно найти в книге С.И.Баранова "Синтез микропрограммных автоматов". Мы же в качестве исходного замкнутого покрытия возьмем множество максимальных классов совместимости Ф = {{1,2},{1,4},{2,3},{3,4,5}}.