1.4 Декомпозиция автомата

1.4.1. Задача декомпозиции

В разделе 1.2.2. для автомата S1 введено понятие реализующий (покрывающий) автомат S.

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

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

Пусть множество А = {1 , 2 , 3 , 4 , 5 , 6}.

Разбиением  множества А называют множество его подмножеств, которые не пересекаются между собой и в объединении дают множество A. Эти подмножества называют блоками разбиения.

Например, для заданного множества разбиением может быть

1(А) = {1234 , 56}.

Назовем одноэлементным разбиением множества А ₀(А) такое разбиение, в котором в каждом блоке содержится только один элемент множества А.

0(А) = {1 , 2 , 3 , 4 , 5 , 6}.

Будем говорить, что разбиение _i_j, если каждый блок разбиения _i входит в какой-нибудь блок разбиения _j.

Рассмотрим пример. Пусть 1(А) = {1234 , 56}, 2(А) = {12 , 34 , 56},

₁(А)  ₂(А)  ₀(А).

3(А) = {15 , 34 , 26},

₁(А) и ₃(А) – не сравнимы.

Произведением разбиений _i(А) и _j(А) назовем разбиение _k(А), которое содержит все непустые пересечения блоков разбиений-сомножителей.

Пример

1(А) = {1234 , 56}, 2(А) = {1256 , 56},

1(А) x 2(А) = {12 , 34 , 56}.

Множество разбиений 1(А), 2(А), …, N(А) называется ортогональным, если произведение всех разбиений равно одноэлементному разбиению множества А.

₁(А) x ₂(А) x … x _N(А) = ₀(А)

Пример. 1(А)={1234, 56}, 2(А) = {1256, 34}, 3(А)={135, 246}.

1(А) x 2(А) x 3(А) = {1 , 2 , 3 , 4 , 5 , 6} = 0(А)

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

Общая теорема декомпозиции: Множеству разбиений {i(А), i=1,N} можно сопоставить абстрактную сеть автоматов, реализующих заданный автомат S, тогда и только тогда, когда П i(А) = 0(А).

1.4.2. Разбиения со свойствами подстановки

Разбиение ={1, 2, , k} называется СП-разбиением (разбиением со свойством подстановки), если из того, что ai и aj находятся в одном блоке, следует, чтоZ. (ai, Z) и (aj,Z) будут находиться в одном блоке.

Если для автомата S СП-разбиение существует, то можно постро-ить автомат S’, для которого состояниями являются имена блоков раз-биения и под действием любого входа из Z он переходит из блока в блок по функции автомата S. Такой автомат называют фактор–автоматом автомата S по разбиению . В этом случае автомат можно представить последовательным соединением автомата S’ и автомата, состояниям которого сопоставлены блоки разбиения, ортогонального с .

Пример. Пусть автомат имеет таблицу переходов (табл. 1.18). Из этой таблицы видно, что разбиение  = {134, 256} будет СП-разбиением.

Обозначим блок 134 как b1, блок 256 как b2, тогда фактор–автомат S’ по этому разбиению будет иметь два состояния, его таблица будет иметь вид табл. 1.19.

Таблица 1.18
	a1	a2	a3	a4	a5	a6
z1	a4	a1	a4	a1	a3	a4
z2	a5	a3	a6	a2	a4	a3

Таблица 1.19
	b1	b2
z1	b1	b1
z2	b2	b1

Выберем в качестве разбиения, ортогонального с , разбиение {15, 32, 46}, обозначим его блоки как с1, с2, c3 и примем их за состоя-ния второго автомата S’’. Тогда исходному автомату будет сопоставлено последовательное соединение автомата S’, на вход которого поступают переменные Z, и автомата S’’, на вход которого поступают переменные Z и выходы автомата S’, совпадающие с его состояниями.

Таблица 1.20
	c1	c2	c3
z1/b1	c3	c3	c1
z1/b2	c2	c1	c3
z2/b1	c1	c3	c2
z2/b2	c3	c2	c2

Описание автомата S’’ приведено в табл. 1.20. Его легко получить, если учесть, что состояниям исходного автомата сопоставлены состояния автоматов S’ и S’’ как в табл.1.21. Например, если состояние автомата S’ –b2 и S’’ –с2, то это соответствует состоянию a2 исходного автомата, и под действием сигнала z1 он должен перейти в a1 (состояние c1 для S’’) , сигнала z2 в a3 (состояние c2 для S’’).

Если для автомата находится СП-разбиение, то его использование может существенно упростить сеть автоматов, получающуюся в результате декомпозиции. Так, если и для автомата S’’ разбиение оказалось бы СП-разбиением, то тогда автомат реализовался бы параллельным соединением двух автоматов, то есть схемы для функций fi были бы не нужны, и сеть имела бы минимальную структуру.

Множество всех СП-разбиений можно построить по следующему алгоритму.

Таблица 1.21
a1	b1c1
a2	b2c2
a3	b1c2
a4	b1c3
a5	b2c1
a6	b2c3

Последовательно рассмотрим все возможные пары состояний исходного автомата. Для каждой пары построим СП-разбиение, при котором данная пара состояний находит-ся в одном блоке. Пусть, например, рассматривается пара a1 и a2. Тогда a1 и a4 должны быть в одном блоке под действием входного сигнала z1, а a5 и a3 в одном блоке под действием сигнала z2. Но если a1,a2,a4 в одном блоке, то a5, a3, a2 должны быть в одном блоке под действием сигнала z2, значит, a1, a2, a3, a4, a5 в одном блоке. Но тогда в этом же блоке будет и a6, потому что если a2 и a3 в одном блоке под действием сигнала z2, то и a5 и a6 должны быть в одном блоке. Значит, если a1 a2 в одном блоке, то в этом же блоке должны быть и все состояния автомата. Получили тривиальный случай, когда все состояния образуют один блок.

Далее рассматриваем случай, когда в одном блоке состояния a1 и a3, потом a1 и a4, и так далее, все (n-1)n вариант. (В нашем случае 5х3=15 вариантов). Полученные нетривиальные варианты затем суммируем попарно между собой, в результате получаем все возможные варианты СП-разбиений.