Минимизация частичного автомата

Определение. Частичным (не полностью определенным) авто-матом называют автомат, у которого d  и/или l определены не полно-стью, значит, у него входные слова могут быть допустимыми и недопус-тимыми. Слово допустимо в состоянии a, если для него возможно опре-делить соответствующее ему выходное слово. Иначе слово будем считать недопустимым в состоянии a .

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

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

1. a_m ~ a_m (рефлексивность),

2. a_m ~ a_n => a_n ~ a_m (симметричность),

3. am ~ ak & an ~ ak Þ am ~ an (нет транзитивности ).

Два состояния am и an совместимы, , если для любого z i Î Z, где функции определены, выполняются два условия:

· d(am,z i) ~ d(an,z i) (условие совместимости по переходу),

· (am,z i) = l(an,z i) (условие совместимости по выходу).

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

Классы совместимости могут пересекаться (в отличие от классов эквивалентности).

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

Классом совместимости также является класс B = d (C, z), если
С - класс совместимости.

Автоматы S1 = <Z1, W1, A1, d1, l1> и S = <Z, W, A, d, l> изоморфны, если они отличаются только именами входов, выходов и состояний.

Говорят, что автомат S1 = <Z1, W1, A1, l1, d1> является подавтоматом автомата S = <Z,W,A,l,d>, если Z ÍZ1, W Í W1, AÍ A1, и функции переходов и выходов автоматов совпадают на множествах Z, W, A. (автомат S1 делает всё то же, что и автомат S, и может быть что-то еще).

Автомат S1 = <Z1, W1, A1, l1, d1> покрывает (реализует) автомат  S= <Z,W,A,l,d>, если он содержит подавтомат S2, который с точностью до имен состояний совпадает с автоматом, покрывающим автомат S, т.е. найдётся подавтомат, изоморфный S.

 

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

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

Далее процесс минимизации частичных автоматов включает в себя три основных этапа:

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

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

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

 

 

Первый этап.

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

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

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

–Х (крест), если состояния am и a s несовместимы по выходу, например а2 и а5 (в таблице выходов в строке Z3 в столбцах a2 и а5 стоят разные выходные сигналы - w1 и w2 соответственно).

–Множество всех пар состояний, следующих за парой (am, a s) и отличных от неё, - все те пары, совместимость которых необходима для совместимости пары (am, a s) по условию совместимости по переходу.

Таблица 1.10
d		a1		a2		a3		a4		a5
z1		a2		a3		a3		--		--
z2		--		a5		a4		a1		--
z3		a3		a2		--		a2		a1
z4		a2		--		a5		--		--
Таблица 1.11
l	a1		a2		a3		a4		a5
z1	w1		w1		w1		--		--
z2	w2		w2		w2		w2		--
z3	--		w1		--		--		w2
z4	w1		--		w1		--		--

Например, для совместимости (а1, а3) необходима совместимость (а2, а3) и (а2, а5), так как (а2, а3) и (а2, а5) следуют за множеством (а1, а3) по входам z1 и z4 соответ-ственно.

–V (птичка), если за (аm, аs) не следуют пары, отличные от (аm, аs), т.е. пара (аm, аs) совместима без дополни-тельных условий, налагае-мых на совместимость дру-гих пар. В нашем примере это пара (а3, а5).

Таблица 1.12
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

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

Таблица 1.13
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) не совместимы.

Будем говорить, что множество состояний В (В ÍА) совместимо с состоянием am Î A (обозначение am~В), если am ~ a s для любого a sÎВ. Рассмотрим способ нахождения максимальных классов совместимости из совместимых пар.

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

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

Продвигаясь влево, записываем для каждого i-го столбца множество состояний Аi ~ ai, т.е. множество всех состояний, соответствующих клеткам без крестов в i-м столбце таблицы.

В нашем примере 3~{4,5} (в третьем столбце таблицы нет крестов в строках 4 и 5).

Каждое Аi пересекаем с каждым членом текущего списка Ф. У нас

А3 = {4, 5} и список Ф также содержит единственный элемент {4, 5}:

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

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

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

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

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

Добавляем в список все пары, состоящие из ai и различных состояний из А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}}.

 

Третий этап

Процедура получения автомата S' = (A', Z', W', d', l'), представляе-мого найденным для исходного автомата S замкнутым покрытием D, достаточно проста. Каждому классу совместимости CiÎD ставится в соответствие состояние ai' нового автомата S'. Для каждого класса Ci Î D и каждого Zi Î Z вычисляется множество следующих за Ci состояний Ti=d(Сi,Zi). Функции переходов определяются как

 Применим эту процедуру к нашему примеру. В качестве исходного замкнутого покрытия, как уже отмечалось выше, возьмем множество максимальных классов совместимости Ф={{1,2},{1,4},{2,3},{3,4,5}} =
{b1, b2, b3, b4}.

Классу совместимости {1,2} ставим в соответствие состояние b1 нового автомата.

 За классом {1,2} по входу Z1 следует класс {2,3}, по входу Z2 - класс {5}, по Z3 - класс {2,3}, по Z4 - {2}. Следовательно, в автомате, получающим-ся в результате совмещения состояний {1,2}, должны быть совместимы состояния {1,2}, {2,3}, {5}, {2,3}, {2}, что в нашем случае верно.

Таким образом, получаем следующие значения функций переходов и выходов: d'(b1, Z1) =b3, d'(b1, Z2)=b4, d'(b1, Z3)=b3, d'(b1, Z4) = b1. l'(b1, Z1) = w1, l'(b1, Z2) = w2, l'(b1, Z3) = w1, l'(b1, Z4) = w1.

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

Таблица 1.15
l	b1	b2	b3	b4
z1	w1	w1	w1	w1
z2	w2	w2	w2	w2
z3	w1	--	w1	w2
z4	w1	w1	w1	w1

Таблица 1.14
d	b1	b2	b3	b4
z1	b3	b1	b3	b3
z2	b4	b1	b4	b2
z3	b3	b3	b1	b1
z4	b1	b1	b4	b4

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

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

В частности, в нашем примере минимальным замкнутым покрыти-ем является {{1,2},{2,3},{4,5}}. Соответствующий этому покрытию мини-мальный автомат имеет всего три состояния (табл.1.16 и табл. 1.17).

 

Таблица 1.16							Таблица 1.17
	{1,2}	{2,3}	{4,5}			{1/2}		{2,3}	{4,5}
z1	{2,3}	{2,3}	–		z1	w1		w1	–
z2	{4,5}	{4,5}	{1,2}		z2	w2		w2	w2
z3	{2,3}	{1,2}	{1,2}		z3	w1		w1	w2
z4	{1,2}	{4,5}	–		z4	w1		w1	–

 

 

Композиция автоматов

 

Рассмотрим основные виды соединений автоматов: параллельное, последовательное, с обратной связью и соединение в сеть.

 

Параллельное соединение

 

Параллельное соединение двух автоматов иллюстрируется на

следующем рисунке:

 

Здесь S1 = < Z1, W1, A1, l1, d1 > и S2 =< Z2, W2, A2, l2, d2 >.

Результирующим автоматом параллельного соединения двух автоматов S1 и S2 назовем автомат S = < Z, W, A, ll, d >, у которого:

Z = Z1 = Z2,

W = F(W1,W2 ),

A = A1 x A2, и для любого ab, где aÎA, bÎB имеет место

l(ab,z) = f(l1 (a,z), l2(b,z)),

d(ab,Z) = d1(a,z), d2(b,z).

 

 

⇐ Предыдущая12345678910Следующая ⇒

Поделиться: