6.2.1. Произведение автоматов

При синхронном режиме работы состояния qQ автомата М определяются прямым произведение состояний автоматов M₁ и M₂,

т. е. q=(q_1i; q_2j)(Q₁Q₂).

Таблица 6.29
q1	q2	q3	q4	q5	q6
(q11; q21)	(q11; q22)	(q12; q21)	(q12; q22)	(q13; q21)	(q13; q22)

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

Пусть автоматы М₁ и М₂ соединены, как показано на рис. 6.15.

При этом X=X₁, Y₁=X₂, Q = (Q₁Q₂) и Y=Y₂.

Функционирование автомата M может быть описано системой:

q[+1]=(q₁[+1]; q₂[+1])=(₁(q₁[]; x₁[]); ₂(q₂[]; ₁(q₁[]; x₁[])));

y[]=(q[]; x[])=₂(q₂[]; ₁(q₁; x₁).

По данным таблиц 6.27, 6.28 и 6.29 составим таблицу поведения автомата М (см. таблицу 6.30).

Последовательное соединение автоматов - некоммутативная операция. При смене мест автоматов М₁ и М₂ меняется структура автомата М и его поведение.

Пусть М1 находился в состоянии q11, а на его вход подан сигнал x11. М1 формирует на выходе сигнал y11=x21 и переходит в состояние q12. . М2 находился в состоянии q21, по сигналу x21 переходит в состояние q21 и формирует на выходе сигнал y21. Следовательно, автомат М переходит из состояния q1=(q11; q21) в состояние q3=(q12; q21) и генерирует на выходе сигнал y21.	таблицу 6.30
	Автомат М
	qQ	xX
		x11	x12
	q1	q3; y21	q1; y22
	q2	q4; y21	q1; y22
	q3	q6; y21	q3; y21
	q4	q6; y21	q4; y21
	q5	q5; y21	q1; y21
	q6	q6; y21	q2; y21

6.2.1.2. Параллельное соединение автоматов

Параллельное соединение автоматов возможно в четырех вариантах (см. рис. 6.16).

Различие схем заключено в формировании входных и выходных сигналов.

Для схем а) и с), множество сигналов на входе автомата М определяется парой входных сигналов автоматов М₁ и М₂, то есть сигнал на входе есть вектор x_i= (x_1j; x_2k)(X₁X₂) (см. таблицу 6.31).

Для схем а) и b) множество сигналов на выходе автомата М определяется парой выходных сигналов автоматов М₁ и М₂, то есть сигнал на выходе есть вектор y_i= (y_1j; y_2k)(Y ₁Y₂) (см. таблицу 6.32).

Для схем b) и d) сигналы на входе автомата М равны входным символам автоматов М₁ и М₂ при условии X₁=X₂=X.

Для схем с) и d) значения сигналов на выходе автомата М определяются оператором , то есть y=(y_1i, y_2j).

.

Таблица 6.31

x1	x2	x3	x4	x5	x6
(x11; x21)	(x11; x22)	(x11; x23)	(x12; x21)	(x12; x22)	(x12; x23)

Таблица 6.32

y1	y2	y3	y4	y5	y6
(y11;y21)	(y11;y22)	(y12;y21)	(y12;y22)	(y13;y21)	(y13;y22)

Система рекуррентных соотношений для схемы а) есть:

Это позволяет вычислить каждую позицию таблицы 33 поведения автомата М.

Например, если дано q₁=(q₁₁, q₂₁) и x₄=(x₁₂, x₂₁), то

q=(₁(q₁₁, x₁₂); ₂(q₂₁, x₂₁))= (q₁₁, q₂₁)= q₁;

y=((q₁₁, x₁₂); (q₂₁, x₂₁))= (y₁₃, y₂₁)=y_5.

(см. таблицы 27-29, 31, 32).

Таблица 6.33
текущее состояние	символы входного алфавита xX
	x1	x2	x3	x4	x5	x6
q1	q3; y1	q4; y1	q3; y2	q1; y5	q2; y5	q1; y6
q2	q4; y1	q4; y1	q3; y2	q2; y5	q2; y5	q1; y6
q3	q5; y1	q6; y1	q5; y2	q3; y1	q4; y1	q3; y2
q4	q6; y1	q6; y1	q5; y2	q4; y1	q4; y1	q3; y2
q5	q5; y1	q6; y1	q5; y2	q1; y3	q2; y3	q1; y4
q6	q6; y1	q6; y1	q5; y2	q5; y3	q2; y1	q1; y4

Для схемы b) на входе автомата М есть x₁=x₁₁=x₂₁, x₂=x₁₂=x₂₂. Тогда система рекуррентных соотношений есть:

Это позволяет вычислить каждую позицию таблицы 34 поведения автомата М.

Например, если дано q₁=(q₁₁, q₂₁) и x₅=(x₁₂, x₂₂), то

q=(₁(q₁₁, x₁₂); ₂(q₂₁, x₂₂))= (q₁₁, q₂₂)= q₂;

y=((q₁₁, x₁₂); (q₂₁, x₂₂))= (y₁₃, y₂₁)=y_5.

(см. таблицы 27-29, 31, 32).

Таблица 6.34

текущее состояние	символы входного алфавита xX
	x1	x5
q1	q3;y1	q2;y5
q2	q4;y1	q2;y5
q3	q5;y3	q1;y1
q4	q6;y3	q4;y1
q5	q5;y1	q2;y1
q6	q6;y1	q2;y1

Для схемы с) выход автомата М формируется функцией

y=(y_1i; y_2j).

Рекуррентные соотношения для такого автомата M есть:

Оператор  формируется поставленной задачей.

Это позволяет вычислить каждую позицию таблицы 35 поведения автомата М.

Например, если дано q₁=(q₁₁, q₂₁), x₅=(x₁₂, x₂₂) и если аргумент функции  содержит символ y₂₁, то на выходе автомата М – формируется символ от автомата М₁, если - y₂₂, то - символ от автомата М₂, то

q=(₁(q₁₁, x₁₂); ₂(q₂₁, x₂₂))= (q₁₁, q₂₂)= q₂;

y=((q₁₁, x₁₂); (q₂₁, x₂₂))= (y₁₃, y₂₁)=y_13.

Таблица 6.35

текущее состояние	символы входного алфавита xX
	x1	x2	x3	x4	x5	x6
q1	q3;y11	q4;y11	q3;y22	q1;y13	q2;y13	q1;y22
q2	q4;y11	q4;y11	q3;y22	q2;y13	q2;y13	q1;y22
q3	q5;y11	q6;y11	q5;y22	q3;y11	q4;y11	q3;y22
q4	q6;y11	q6;y11	q5;y22	q4;y11	q4;y11	q3;y22
q5	q5;y11	q6;y11	q5;y22	q1;y12	q2;y12	q1;y22
q6	q6;y11	q6;y11	q5;y22	q5;y12	q2;y11	q1;y22

Для автомата по схеме d) сигнал на входе формируется также как для автомата по схеме b), а сигнал на выходе также как для автомата по схеме с).

Система рекуррентных соотношений есть:

Например, если дано q₁=(q₁₁, q₂₁), x₅=(x₁₂, x₂₂) и если аргумент функции  содержит символ y₂₁, то на выходе автомата М – формируется символ от автомата М₁, если - y₂₂, то - символ от автомата М₂:

q=(₁(q₁₁, x₁₂); ₂(q₂₁, x₂₂))= (q₁₁, q₂₂)= q₂;

y=((q₁₁, x₁₂); (q₂₁, x₂₂))= (y₁₃, y₂₁)=y_13.

Таблица 6.36

текущее состояние	символы входного алфавита xX
	x1	x5
q1	q3;y11	q2;y13
q2	q4;y11	q2;y13
q3	q5;y12	q1;y11
q4	q6;y12	q4;y11
q5	q5;y11	q2;y11
q6	q6;y11	q2;y11