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

Разбиение p={p1, p2, ¼, pk} называется СП-разбиением (разбиением со свойством подстановки), если из того, что ai и aj находятся в одном блоке, следует, что"Z. d(ai, Z) и d(aj,Z) будут находиться в одном блоке.

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

Пример. Пусть автомат имеет таблицу переходов (табл. 1.18). Из этой таблицы видно, что разбиение p = {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

 

Выберем в качестве разбиения, ортогонального с p, разбиение
{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 вариантов). Полученные нетривиальные варианты затем суммируем попарно между собой, в результате получаем все возможные варианты СП-разбиений.

 

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

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

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

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

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

 

Таблица 1.22
d/l	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

 

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

Будем считать для выбранного примера, что алфавиты состояний компонентных автоматов 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 на внешнее воздействие z i, при условии, что автомат 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 разбиения t_i на множестве А так, чтобы для любых а_k и а_m из множества А условие:

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

t1 = {136 , 24 , 5} , t2 = {1234 , 56}, t₃ = {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 разбиения h_i на множестве Z так, чтобы для любых Z_k и Z_m из множества Z условие: "aÎA F_i (a, Z_k) = F_i(a , Z_m) выполнялось тогда и только тогда, когда Z_k и Z_m принадлежат к одной группе разбиения h_i.

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

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

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

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

S_i = ( A_i , Z_i , d_i ); A_i = { p_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>`` = h_i.

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

Если p_ix(p_k x p_l x…xp_m)£t_i, то Z_i` = (p_k x p_l x … x p_m).

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

p1(A)xp2(A) = {12, 56, 34}

p1(A) x p3(A) = { 13 , 5 , 24 , 6 } 

 p2(A) x p3(A) = { 15 , 26 , 3 , 4 }

p1(A) x p2(A) x p3(A)={ 1 , 2 , 3 , 4 , 5 , 6 }

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

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

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

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

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

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

p2(A) x p1(A) ={13 , 5 , 24 , 6 }

t2 > p2(A) x p1(A), => Z2`=p1(A)={1234 ,56 }={b1, b2} = B,

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

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

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

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

t3 = { 14 , 23 , 5 , 6 }

p1(A) x p2(A) x p3(A) = { 1, 2, 3, 4, 5, 6}.

t3 > p3(A) x p1(A) x p2(A)=> Z3`=p1(A)xp2(A)={12, 56, 34}={p1, p2, p3} = P,

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

d₃: D x ( P x V) ® D

 

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

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

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

 

 

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

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

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

 

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

 

Упражнения

 

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

Поделиться: