1.3. Композиция автоматов

    Рассмотрим основные виды соединений автоматов: параллельное, последовательное, с обратной связью и соединение в сеть.

1.3.1. Параллельное соединение

Параллельное соединение двух автоматов иллюстрируется на

следующем рисунке:

З десь S1 = < Z1, W1, A1, 1, 1 > и S2 =< Z2, W2, A2, 2, 2 >.

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

Z = Z1 = Z2,

W = F(W1,W2 ),

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

(ab,z) = f(1 (a,z), 2(b,z)),

(ab,Z) = 1(a,z), 2(b,z).

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

S1=<Z1,W1,A1 1,1>, S2=<Z2,W2,A2,2,2>

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

Z = Z1;

W = W2;

W1= Z2;

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

 (ab,z) =  2(b, 1(a,z));

(ab,z) = (1(a,z), 2(b, 1(a,z))).

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

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

Р ис.1.10

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

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

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

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

Определение

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

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

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

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

,

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

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

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

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

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

1
Z1	x1
Z2	x1
Z3	x2
Z4	x3

1	b1	b2	b3
x1	b1	b1	b3
x2	b3	b2	b3
x3	b3	b2	b1

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

2
Z1	y1
Z2	y2
Z3	y1
Z4	y2

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

2	c1	c2
q1y1	c1	c1
q1y2	c2	c1
q2y1	c1	c2
q2y2	c2	c2

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

3
Z1	t1
Z2	t2
Z3	t1
Z4	t2

f3
c1	p1
c2	p2

3	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 состояний. Введенные понятия сети автоматов и ее результирующего автомата позволяют сформулировать задачу композиции автоматов – для заданной сети описать автомат, реализуемый сетью.