Последовательное соединение

 

S1=<Z1,W1,A1 l1,d1>, S2=<Z2,W2,A2,l2,d2>

 

 

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

Z  =  Z1;

W = W2;

W1= Z2;

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

l (ab,z) = l 2(b, l1(a,z));

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

 

Соединение с обратной связью

 

Композиция приведена на рис.1.10

 

 

Рис.1.10

В этой композиции, если автомат S1 находится в состоянии a, автомат S2 – b, то значение z1=F(z, l2(b,w))= F(z, l2(b, l1(z1, a))). Получили некорректность, когда z1 зависит от z1.

Этой некорректности можно избежать, если положить, что хотя бы один из автоматов S1 и S2 являются автоматами Мура. Например, если таковым является автомат S1, то в последней формуле равенства будет стоять F(z, l2(b, l1(a))).

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

 

 

Соединение в сеть

Определение

Компонентным автоматом (полуавтоматом Мура) называют автомат Мура, в котором каждому состоянию поставлен в соответствие свой выходной сигнал, отличный от выходных сигналов других состояний.

Говорят, что в таких автоматах обеспечена полнота выходов.

Определение.

Сетью автоматов назовем шестерку N = <Z,W,{Si},{fi},{wi},g> (i = 1...n),
где : Z - множество входов сети, W - множество выходов сети, Si - компонентный автомат сети с алфавитом входов Zi и алфавитом выходов Ai. Алфавит Zi = Z'I x Z''i поясняется рис. 1.11.

 

 

,

 

 

fi : A1 x...x An -> Zi'',      wi : Z -> Zi',    ,
n - количество компонентных автоматов.

 

Выходная функция g определяет выход сети.  g: A1 x...x An x Z -> W (рис.1.12).

Множество Si составляeт базис сети, множество {fi} определяeт её структуру.

 

Пример. Рассмотрим сеть, показанную на рис. 1.13.

1-я компонента:

w1   Z1 x1 Z2 x1 Z3 x2 Z4 x3

d1 b1 b2 b3 x1 b1 b1 b3 x2 b3 b2 b3 x3 b3 b2 b1

 

2-я компонента:

w2   Z1 y1 Z2 y2 Z3 y1 Z4 y2

f2 d1 d2 b1 q1 q2 b2 q1 q1 b3 q1 q1

d2 c1 c2 q1y1 c1 c1 q1y2 c2 c1 q2y1 c1 c2 q2y2 c2 c2

3-я компонента:

w3   Z1 t1 Z2 t2 Z3 t1 Z4 t2

f3   c1 p1 c2 p2

d3 d1 d2 p1t1 d2 d1 p1t2 d1 d2 p2t1 d1 d2 p2t2 d1 d1

Выход:

g	d1	d2
c1	w1	w2
c2	w1	w1

Сеть реализует автомат (результирующий автомат сети), состояния которого определяются как A1xA2X¼An.

Для приведённого примера автомат имеет 3 * 2 * 2 = 12 состояний. Введенные понятия сети автоматов и ее результирующего автомата позволяют сформулировать задачу композиции автоматов – для заданной сети описать автомат, реализуемый сетью.

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

 

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

 

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

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

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

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

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

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

p1(А) = {1234 , 56}.

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

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

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

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

p₁(А) ³ p₂(А) ³ p₀(А).

p3(А) = {15 , 34 , 26},

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

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

Пример

p1(А) = {1234 , 56}, p2(А) = {1256 , 56},

p1(А) x p2(А) = {12 , 34 , 56}.

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

p₁(А) x p₂(А) x … x p_N(А) = p₀(А)

Пример. p1(А)={1234, 56}, p2(А) = {1256, 34}, p3(А)={135, 246}.

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

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

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

 

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

Поделиться: