Решение:

Множество вершин X = {x₁, x₂, x₃, x₄, x₅, x₆}.

Вершины графа отожествляются с состояниями автомата таким образом, что множество состояний Q = {q₁, q₂, q₃, q₄, q₅, q₆}. Переход автомата из одного состояния в другое осуществляется под воздействием множества входных сигналов X={x₁, x₂, x₃, x₄}. Автомат позволяет вырабатывать выходные сигналы Y={y₁, y₂, y₃}.

На основании аналитического описания ориентированного графа из задания № 1 запишем закон отображения состояний автомата:

Гq₁ = { q₁(x₄/y₁), q₃(x₃/y₂), q₄(x₂/y₂), q₆(x₁/y₂)},

Гq₂ = {q₃(x₃/y₂), q₄(x₄/y₂)},

Гq₃ = { q₁(x₁/y₃), q₂(x₂/y₃), q₅(x₃/y₂)},

Гq₄ = {q₁(x₃/y₃), q₂(x₁/y₃), q₆(x₄/y₂)},

Гq₅ = {q₃(x₃/y₃)},

Гq₆ = {q₁(x₁/y₃), q₄(x₄/y₃)}.

Обобщенная таблица переходов и выходов соответствующего конечного автомата представлена в табл. 2.

Таблица 2

X	Q	q1	q2	q3	q4	q5	q6
X1		q6/y2	─	q1/y3	q2/y3	─	q1/y3
X2		q4/y2	─	q2/y3	─	─	─
X3		q3/y2	q3/y2	q5/y2	q1/y3	q3/y3	─
X4		q1/y1	q4/y2	─	q6/y2	─	q4/y3

Осуществим структурный синтез автомата, заданного табл. 1. В качестве элементов памяти используем T-триггеры, в качестве элементной базы используем логические элементы И-ИЛИ-НЕ.

Количество букв входного алфавита n = 4

Количество входов p ≥ log₂ n = log₂ 4 = 2;

Количество букв выходного алфавита m = 3

Количество выходов e ≥ log₂ m = log₂ 3 = 2;

Количество состояний r = 6

Количество триггеров z ≥ log₂ r = log₂ 6 = 3.

Приступаем к кодированию:

	u	u1	u2
x1		1	0	4
x2		1	1	2
x3		0	0	5
x4		0	1	4

	v1	v2
y1	1	0	1
y2	0	1	7
y3	0	0	7

q	w	w1	w2	w3
q1		0	0	0	4
q2		1	0	0	2
q3		0	0	1	3
q4		0	1	0	3
q5		0	1	1	1
q6		1	1	0	2

На основании результатов кодирования строим обобщенную таблицу переходов и выходов структурного автомата (табл.3), заменяя состояния, входные и выходные переменные их кодами.

Таблица 3

u1u2	w1w2w3	000	100	001	010	011	110
10		110/01	─	000/00	100/00	─	000/00
11		010/01	─	100/00	─	─	─
00		001/01	001/01	011/01	000/00	001/00	─
01		000/10	010/01	─	110/01	─	010/00

Используя таблицу переходов T-триггера и данные предыдущей таблицы, составим обобщенную таблицу функционирования структурного автомата (табл.4). Функции возбуждения трех триггеров обозначены через T₁, T₂, T₃, соответственно.

Таблица 4

u1	u2	w1(t)	w2(t)	w3(t)	w1 (t+1)	w2 (t+1)	w3 (t+1)	v1	v2	T1	T2	T3
1	0	0	0	0	1	1	0	0	1	1	1	0
1	1	0	0	0	0	1	0	0	1	0	1	0
0	0	0	0	0	0	0	1	0	1	0	0	1
0	1	0	0	0	0	0	0	1	0	0	0	0
1	0	1	0	0	*	*	*	*	*	*	*	*
1	1	1	0	0	*	*	*	*	*	*	*	*
0	0	1	0	0	0	0	1	0	1	1	0	1
0	1	1	0	0	0	1	0	0	1	1	1	0
1	0	0	0	1	0	0	0	0	0	0	0	1
1	1	0	0	1	1	0	0	0	0	1	0	1
0	0	0	0	1	0	1	1	0	1	0	1	0
0	1	0	0	1	*	*	*	*	*	*	*	*
1	0	0	1	0	1	0	0	0	0	1	1	0
1	1	0	1	0	*	*	*	*	*	*	*	*
0	0	0	1	0	0	0	0	0	0	0	1	0
0	1	0	1	0	1	1	0	0	1	1	0	0
1	0	0	1	1	*	*	*	*	*	*	*	*
1	1	0	1	1	*	*	*	*	*	*	*	*
0	0	0	1	1	0	0	1	0	0	0	1	0
0	1	0	1	1	*	*	*	*	*	*	*	*
1	0	1	1	0	0	0	0	0	0	1	1	0
1	1	1	1	0	*	*	*	*	*	*	*	*
0	0	1	1	0	*	*	*	*	*	*	*	*
0	1	1	1	0	0	1	0	0	0	1	0	0

По этой таблице запишем СДНФ выходных функций V и функций возбуждения триггеров T₁, T₂, T₃, зависящих от набора переменных u₁, u₂, w₁(t), w₂(t), w₃(t). В результате получим систему логических функций для построения комбинационной части автомата:

.

.

.

.

.

.

Минимизируем функции согласно картам Карно:

.

Функциональная схема структурного автомата:

18