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

Композиция автоматов M₁ и M₂ при синхронном режиме их работы есть автомат M=X;Y;Q;, внутренние состояния которого q=(q_1i;q_2j)(Q₁Q₂) приведены в таблице 1.72.

Таблица 2.3

q1	q2	q3	q4	q5	q6
(q11;q21)	(q11;q22)	(q12;q21)	(q12;q22)	(q13;q21)	(q13;q22)

2.1.1.Последовательное соединение двух автоматов

Пусть автоматы М₁ и М₂ работают в синхронном режиме и соединены так, как показано на рис. 1.25. При этом имеем X=X₁, Y₁=X₂, Q = (Q₁  Q₂) и Y=Y₂.

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

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

(2.1)

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

Таблица 2.4

Автомат M
текущее состояние qQ		символы входного алфавита xX=X1
		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

Рис.2.6 Граф композиции автоматов М1 и М2 .

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

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

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

Таблица поведения такого автомата представлена таблицей 2.5, а граф - рис. 2.8.

Таблица 2.5

Автомат M
текущее состояние qQ		символы входного алфавита xX=X2
		x21		x22		x23
q1	q3;y11		q2;y11		q1y13
q2	q4;y11		q4;y11		q1;y13
q3	q5;y12		q6;y12		q3;y11
q4	q6;y12		q6;y12		q3;y11
q5	q5;y11		q6;y11		q1;y11
q6	q6;y11		q6;y11		q1;y11

Рис. 2.8 Граф композиции автоматов М₂ и М_1.

Сравнение таблиц поведения и графов двух автоматов подтверждает некоммутативность последовательного соединения двух автоматов. Часто операцию последовательного соединения автоматов называют их суперпозицией.

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

Пусть автоматы М1 и М2 работают в синхронном режиме и соединены так, как показано на рис. 2.9.

Рис. 2.9 Схемы параллельного соединения автоматов М₁ и М₂.

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

Для схемы на рис. 2.9а) множество входных символов автомата М определяется парой входных символов автоматов М₁ и М₂, то есть x_i= (x_1j;x_2k)(X₁X₂) (см. таблицу 2.6), а множество выходных символов - парой выходных символов автоматов М1 и М2 y_i=(y_1j;y_2k)(Y₁Y₂) (см. таблицу 2.7).

Таблица 2.6

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

Таблица 2.7

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

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

(2.2)

Смена состояний и формирование выходных символов в каждом автомате сети происходит независимо и одновременно. Такая схема позволяет исследовать сложные автоматы, имеющие несколько входов и выходов. Таблица поведения композиции автоматов, реализованной по схеме на рис. 2.9а), представлена таблицей 2.8, а граф - рис. 2.10.

Таблица 2.8

текущее состояние qQ	символы входного алфавита 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

Рис. 2.10 Граф композиции двух автоматов по схеме на рис.2.9а).

Для схемы на рис. 2.9b) входные символы автомата М одновременно и одинаковые поступают на входы автоматов М₁ и М₂. Их количество ограничено меньшим входным алфавитом автоматов М₁ и М₂. Пусть x₁=x₁₁=x₂₁, x₅=x₁₂=x₂₂, а x₂₃ - не определен. Выходные символы автомата М совпадают с символами для схемы на рис. 2.9а).Функционирование такого автомата M может быть описано системой рекуррентных соотношений:

(2.3)

Таблица поведения композиции автоматов, реализованной по схеме на рис. 2.9b), представлена таблицей 2.9. На рис. 2.11 показан граф этого автомата.

Таблица 2.9

текущее состояние qQ	символы входного алфавита 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

Рис. 2.11 Граф композиции двух автоматов по схеме на рис.2.9b).

Для схемы на рис. 2.9с) входные символы автомата М совпадают с символами для схемы на рис. 2.9а), а выходные символы определяются функцией y=y_1i;y_2j), значения которой зависят от выходных символов автоматов М₁ и М₂.

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

(2.4)

Оператор  определяется поставленной задачей автомату М:

:(Y₁Y₂)Y. (2.5)

Например, это может быть оператор условного перехода. Пусть если аргумент функции y_1i;y_2j) содержит символ y₂₁, то на выходе автомата М генерируется выходной символ автомата М₁ соответствующей пары y_1i;y_2j), если - символ y₂₂, то - выходной символ автомата М₂.

Таблица поведения композиции автоматов, реализованной по схеме на рис. 2.9c), представлена таблицей 2.10, а граф - рис. 2.12.

Таблица 2.10

текущее состояние qQ	символы входного алфавита 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

Рис. 2.12 Граф композиции двух автоматов по схеме на рис.2.9с).

Для схемы на рис. 2.9d) входные символы автомата М совпадают с символами схемы на рис. 2.9b), а выходные - с символами схемы на рис. 2.9 с).

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

(2.5)

Таблица поведения композиции автоматов, реализованной по схеме на рис. 2.9d), представлена таблицей 2.11, а граф - рис. 2.13.

Таблица 2.11

текущее состояние qQ	символы входного алфавита 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

Рис. 2.13 Граф композиции двух автоматов по схеме на рис.2.9d).