Соединение автоматов. Параллельное соединение двух автоматов. Соединение двух автоматов с обратной связью, страница 3

S₁=(A₁, Z¹, W, d₁, l₁,a₁₁)

S₂=(A₂, W, W², d₂, l₂,a₁₂)

Проводя замену, «объединяя» автоматы получим новый автомат S, у которого:

·  внутренний алфавит образуется из всевозможных пар состояний автоматов S₁ и S₂:

A = A₁*A₂.

·  входной алфавит есть функциональная зависимость j от W² и z_f:

Z¹= j(W², z_f)

·  новая функция переходов формируется зависимостью от d₁, d₂ и текущего элемента входного алфавита z_f :

d(a_m, z_f) = (d(a_m1, j(z_f, l₂(a_m2))), d(a_m2, l₁(a_m1, j(z_f, l₂(a_m2)))))

·  новая функция выхода формируется в зависимости j от функций l₁, l₂ текущего элемента входного алфавита z_f :

l(a_m, z_f) = l₁(a_m1, j(z_f, l₂(a_m2)))

ПРИМЕР:

Пусть имеется соединение автоматов S₁ и S₂ c обратной связью. S₂ – автомат Мура:

 

Автоматы определяются двумя векторами:

S₁=(A, Z¹, W, d₁, l₁,a₁)

S₂=(B, W, W², d₂, l₂,b₁)

Таблицы переходов и выходов автомата S₁:

d₁:                                                                               l₁:

	b1	b2
W1	b1	b2
W2	b2	b2
W3	b1	b1
	W21	W22

Таблица функции j:

j:

	W21	W22
Z1	Z11	Z12
Z2	Z11	Z12
Z3	Z11	Z11

Построим таблицу выходов нового автомата, руководствуясь следующими правилами:

• в верхней строке выписываются состояния нового автомата – a_ib_j;
• в соответствие a_ib_j и z_f в ячейки таблицы l по таблице l₁ выписываются выходные сигналы W_k;

l:

	a1b1	a1b2	a2b1	a2b2	a3b1	a3b2
Z1	W1	W3	W2	W1	W1	W2
Z2	W1	W3	W2	W1	W1	W2
Z3	W1	W1	W2	W2	W1	W1

Так как внутренний алфавит определяется формулой: A = A₁*A_2, таблица переходов нового автомата будет выглядеть следующим образом:

d:

	a1b1	a1b2	a2b1	a2b2	a3b1	a3b2
Z1	a2b1	a2b1	a2b2	a3b2	a1b1	a3b2
Z2	a1b1	a2b1	a2b2	a3b2	a1b1	a3b2
Z3	a1b1	a1b2	a2b2	a2b2	a1b1	a1b2

Составляется таблица следующим образом:

• в верхней строке выписываются в порядке возрастания индексов всевозможные варианты a_ib_j;
• в соответствие a_i и Z_k в ячейки таблицы d по таблице d₁ выписываются состояния a_j;
• в соответствие b_i и Z_k в ячейки таблицы d по таблице dl выписываются состояния b_j;

Наш новый автомат S, замещающий S₁ и S₂ задан таблицами l и d.

При составлении таблиц следует следить за последовательностью своих действий и не забывать, что в автомате Мура (S₂) каждому состоянию соответствует свой выходной сигнал. Другой автомат (в нашем случает S₁) зависит от выходного сигнала первого автомата.