1.4.3. Метод декомпозиции

Рассмотрим метод на примере автомата, представленного в табл.1.22. Алфавит состояний А = {1, 2, 3, 4, 5, 6},

алфавит входов Z = { z₁ , z₂ , z₃ , z₄ },

алфавит выходов W = {w₁ , w₂ , w₃}.

Нетрудно убедиться, что для этого автомата СП-разбиения нет.

Таблица 1.22
/	1	2	3	4	5	6
z1	2 / w1	5 / w1	1 / w1	6 / w1	1 / w3	2 / w2
z2	6 / w2	1 / w1	5 / w3	2 / w2	1 / w1	6 / w2
z3	6 / w1	1 / w1	5 / w1	2 / w2	2 / w3	5 / w3
z4	2 / w3	5 / w3	1 / w1	6 / w3	4 / w1	3 / w1

Выберем разбиения множества состояний А: 1(А)={1234, 56}, 2(А) = {1256, 34}, 3(А)={135, 246}, т.е. сеть будет состоять из трёх компонентных автоматов. Условие теоремы выполняется, ₁(А), ₂(А) и ₃(А) – ортогональны.

Будем считать для выбранного примера, что алфавиты состояний компонентных автоматов A, B и С.

p1(А) = { 1234 , 56} = { b1 , b2} = B.

p2(А) = {1256 , 34} = {c1 , c2} = C.

p3(А) = {135 , 246} = {d1 , d2} = D.

Так, например, если автомат В (соответствующий разбиению p1(А)) находится в состоянии b1, автомат С (соответствующий разбиению p2(А)) – в состоянии с2, автомат D (соответствующий разбиению p2(А)) – в состоянии d1, то автомат SN будет находиться в состоянии 3. Выбор разбиений p1, p2, p3 определяет сложность функций fi, а от нее – со сколькими автоматами связан автомат S_i.

Для каждого разбиения pi построим функцию Fi: AxZ®pI на базе функции d. Эта функция определяет реакции автоматов Si на внешнее воздействие zi, при условии, что автомат S (и реализующий его автомат SN) находится в состоянии k.

Таблица 1.23
F1	1	2	3	4	5	6
z1	b1	b2	b1	b2	b1	b1
z2	b2	b1	b2	b1	b1	b2
z3	b2	b1	b2	b1	b1	b2
z4	b1	b2	b1	b2	b1	b1

Определим для функций F_i разбиения _i на множестве А так, чтобы для любых а_k и а_m из множества А условие:

ZZ Fi (ak, z)=Fi (am , z) выполнялось тогда и только тогда, когда ak и am принадлежат к одной группе разбиения i. (табл.1.23 -1.25).

1 = {136 , 24 , 5} , 2 = {1234 , 56}, ₃ = {14 , 23 , 5, 6},

Таблица 1.24
F2	1	2	3	4	5	6
Z1	c1	cl	cl	cl	cl	cl
Z2	cl	cl	cl	cl	cl	cl
Z3	cl	cl	cl	cl	cl	cl
Z4	cl	cl	cl	cl	c2	c2

Таблица 1.25
F3	1	2	3	4	5	6
Z1	d2	dl	dl	d2	dl	d2
Z2	d2	dl	dl	d2	dl	d2
Z3	d2	dl	dl	d2	d2	dl
Z4	d2	dl	dl	d2	d2	dl

Определим для функции F_i разбиения _i на множестве Z так, чтобы для любых Z_k и Z_m из множества Z условие: aA F_i (a, Z_k) = F_i(a , Z_m) выполнялось тогда и только тогда, когда Z_k и Z_m принадлежат к одной группе разбиения _i.

₁ = {z₁ z₄ , z₂ z₃} ₂ = {z₁ z₂ z₃ , z₄};

₃ = {z₁ z₂ , z₃ z₄}.

Построим сеть N = < Z_N , W_N , {S_i} , {f_i} , {_i} , g > Z_N = Z, W_N = W.

2) S_i , f_i , _i - определяют компонентные автоматы;

S_i = ( A_i , Z_i , _i ); A_i = { _i } – блоки разбиения;

Z_i = Z_i` x Z<sub>i</sub>``, если Z<sub>i</sub>` не пустое множество,

Z_i = Z_i``, если Z<sub>i</sub>` пустое множество, Z<sub>i</sub>`` = _i.

Z_i` определяются по следующему правилу:

Если _ix(_k x _l x…x_m)_i, то Z_i` = (_k x _l x … x _m).

Найдём все возможные произведения пересечений.

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

1(A) x 3(A) = { 13 , 5 , 24 , 6 }

2(A) x 3(A) = { 15 , 26 , 3 , 4 }

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

Определим зависимость функции переходов первого автомата от других автоматов.

Таблица 1.26
1	b1	b2
d1,u1	b1	b1
d1,u2	b2	b1
d2,u1	b2	b1
d2,u2	b1	b2

1 > 1(A) x 3(A), => Z1` = 3(A) = {135, 246} = { d1 , d2} = D. Первый автомат зависит от третьего.

₁ = {z₁ z₄ , z₂ z₃} = {u1 , u2} = U.

₁: B x ( D x U )  B Функция переходов представлена в табл.1.26, композиция – на рис.1.14

Определим зависимость функции переходов второго автомата от других автоматов

 2(A) x 1(A) ={13 , 5 , 24 , 6 }

2 > 2(A) x 1(A), => Z2`=1(A)={1234 ,56 }={b1, b2} = B,

₂ ={Z₁, Z₂, Z₃, Z₄}={v1, v2}=V,

Таблица 1.27
2	с1	с2
b1,v1	с1	с1
b1,v2	с1	с1
b2,v1	с1	*
b2,v2	c2	*

₂:Bx(BxV)C. Функция переходов представлена в табл.1.27, композиция – на рис.1.15

* - такое событие невозможно, т.к. с2 обозначает состояния 3 или 4 результирующего автомата S_N, a b2 – состояния 5 или 6, поэтому, если автомат С находится в состоянии с2, то b2 не может поступать на его вход.

Определим зависимость функции переходов второго автомата от других автоматов

3 = { 14 , 23 , 5 , 6 }

1(A) x 2(A) x 3(A) = { 1, 2, 3, 4, 5, 6}.

3 > 3(A) x 1(A) x 2(A)=> Z3`=1(A)x2(A)={12, 56, 34}={p1, p2, p3} = P,

₃ = { Z₁ Z₂ , Z₃ Z₄ } = { v1 , v2 } = V,

₃: D x ( P x V)  D

Таблица 1.28
3		d1	d2
p1,v1	b1,c1,v1	d2	d1
p1,v2	b1,c1,v2	d2	d1
p2,v1	b2,c1,v1	d1	d2
p2,v2	b2,c1,v2	d1	d2
p3,v1	b1,c2,v1	d1	d2
p3,v2	b1,c2,v2	d2	d1

Функция ₃ имеет вид, показанный в табл. 1.28.

Функция переходов представлена в табл.1.28, композиция –на рис.1.16.

Создадим разбиение множества P x V:

Q = { (p1,v1) (p1,v2) (p3,v2) , (p2,v1) (p2,v2) ( p3,v1) } = {q1, q2}.

Тогда функция ₃ принимает вид, показанный в табл.1.29.

Таблица 1.29
3	d1	d2
q1	d2	d1
q2	d1	d2

Выходная функция представлена в табл.1.30, композиция –на рис.1.17.

Таблица1.30
g	b1,c1,d1	b1,c1,d2	b1,c2,d1	b1,c2,d2	b2,c1,d1	b2,c1,d2
	1	2	3	4	5	6
z1	w1	w1	w1	w1	w3	w2
z2	w2	w1	w3	w2	w1	w2
z3	w1	w1	w1	w2	w3	w3
z4	w3	w3	w1	w3	w1	w1