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

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

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

Пусть существует множество состояний автомата S:

 

S= { 1, 2, 3, 4, 5, 6 }. (1.17)

 

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

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

 

p₁(S) = { 1234, 56 }.

 

Одноэлементным разбиением множества S p₀(S) называется такое разбиение, в котором в каждом блоке содержится ровно 1 элемент множества S.

p₀(S) = { 1, 2, 3, 4, 5, 6 }.

 

p разбиения можно сравнивать между собой по величине элементов. Разбиение p_i £ p_j, если каждый блок разбиения p_i входит в какой-нибудь блок разбиения p_j.

Например, пусть множество S (1.17) имеет три p разбиения: разбиение p₁(S) = { 1234, 56 }, p₂(S)={12, 34, 56} и p₃(S) = { 15, 34, 26 }. При сравнении разбиений p₁ и p₂ следует, что p₁(S) ³ p₂(S) так как все блоки разбиения p₂ полностью входят в блоки разбиения p₁. При сравнении разбиения p₃ с разбиениями p₁ или p₂ можно сделать вывод, что данные разбиения нее сравнимы, так как блоки ни одно из разбиений полностью не входят друг в друга.

Произведением разбиений p_i(S) и p_j(S) называется разбиение p_k(S) такое, что p_i(S) ³ p_k(S) и p_j(S) ³ p_k(S) и не найдётся разбиение p_m(S) множества S p_m(S) > p_k(S), удовлетворяющего условиям: p_i(S) ³ p_m(S) и p_j(S) ³ p_m(S).

Например для разбиений p₁(S) = {1234, 56 } и p₂(S) = { 1256, 34 } произведением будет разбиение p_k(S) = p₁(S) x p₂(S) = { 12, 34, 56 }. Разбиение p_k(S) получается перемножением каждого блока разбиений p₁(S) и p₂(S) между собой (1234 х 1256 = 12; 1234 х 34 = 34 и т.д.). Произведение разбиений содержит все непустые пересечения блоков разбиений-сомножителей.

Множество разбиений p₁(S), p₂(S), …, p_n(S) называется ортогональным, если произведение всех разбиений равно одноэлементному разбиению множества S, т.е. p₁(S) x p₂(S) x … x p _n(S) = p₀(S).

Например выберем для множества состояний S (1.17) разбиения

p₁(S) = { 1234, 56 }, p₂(S) = { 1256, 34 } и p₃(S) = { 135, 246 }. Проверка показывает, что p₁(S) x p₂(S) x p₃(S) = { 1, 2, 3, 4, 5, 6 } = p₀(S).

Рассмотрим последовательность вычислений:

p_k(S) = p₁(S) x p₂(S) = { 12, 34, 56 };

p_k(S) x p₃(S) = { 1, 2, 3, 4, 5, 6 }.

Это означает, что разбиения p₁(S), p₂(S) и p₃(S) – ортогональны.

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

 

. (1.18)