3. Построение графа переходов абстрактного автомата и таблицы переходов-выходов

Построим по таблице 1.2 граф переходов автомата Мура. Будем при этом предполагать, что последний символ каждого входного слова должен переводит автомат в начальное состояние.

В момент времени t = 0 автомат находится в состоянии a₁. При подаче в последующие моменты времени каждого входного сигнала z(t) автомат переходит в новое состояние и вырабатывает выходной сигнал w(t).

Поскольку для абстрактного автомата порядок нумерации состояний, отличных от начального, безразличен, можно считать, что буква z(1) = 0 первого входного слова из таблицы 1.2 переводит автомат в состояние a₂. При этом вырабатывается выходной сигнал w(1) = . Буква z(2) = 0 переводит автомат из состояния a₂ в состояние a₃ и обеспечивает выработку выходного сигнала w(2) = . Буква z(3) = 0 переводит автомат из состояния a₃ в состояние a₄ и обеспечивает выработку выходного сигнала w(3) =  и т.д. Последней в первом входном слове буквой z(7) =  автомат должен переводиться в состояние a₁. Этому переходу соответствует выходной сигнал w(7) = 0. Начальные отрезки z(1)z(2)z(3), w(1)w(2)w(3) второго входного и выходного слов совпадают с соответствующими начальными отрезками первого входного и выходного слов, поэтому первые три перехода для второго входного слова совпадают с уже построенными. Последующие переходы для этого слова строятся точно так же, как и для первого слова. Затем строятся переходы для остальных входных и выходных слов. Граф переходов заданного автомата представлен на рисунке 1.1.

1. Таблица 1.2 Таблица переходов-выходов проектируемого автомата

y	a	0	1	
0	a0’	a1	a2	-
1	a0”	a1	a2	-
β	a1	a3	a4	-
β	a2	a5	a6	-
β	a3	a7	a8	-
β	a4	a9	a10	-
β	a5	a11	a12	-
β	a6	a13	a14	-
β	a7	a15	a16	-
β	a8	a17	a18	-
1	a9	a19	a20	-
0	a10	a21	a22	-
β	a11	a23	a24	-
1	a12	a25	a26	-
1	a13	a27	a28	-
0	a14	a29	a30	-
1	a15	-	-	a31
0	a16	-	-	a32
1	a17	-	-	a33
0	a18	-	-	a34
1	a19	-	-	a35
0	a20	-	-	a36
0	a21	-	-	a37
1	a22	-	-	a38
1	a23	-	-	a39
0	a24	-	-	a40
0	a25	-	-	a41
1	a26	-	-	a42
1	a27	-	-	a43
0	a28	-	-	a44
1	a29	-	-	a45
0	a30	-	-	a46
1	a31	-	-	a47
1	a32	-	-	а48
1	a33	-	-	а49
0	a34	-	-	а50
1	a35	-	-	a0’
1	a36	-	-	a0’
0	a37	-	-	a0”
1	a38	-	-	a0’
0	a39	-	-	а51
0	a40	-	-	а52
0	a41	-	-	a0’
0	a42	-	-	a0”
1	a43	-	-	a0’
0	a44	-	-	a0”
1	a45	-	-	a0”
0	a46	-	-	a0'
1	a47	-	-	a0”
0	a48	-	-	a0'
0	a49	-	-	a0”
1	a50	-	-	a0'
0	a51	-	-	a0'
1	a52	-	-	a0'

2. Таблица 1.3 Упрощенная таблица переходов-выходов проектируемого автомата

y	A	0	1	
0	b0'	b1	b2	-		b0'	=	a0’
1	b0"	b1	b2	-		b0"	=	a0”
Β	b1	b3	b4	-		b1	=	a1
Β	b2	b5	b6	-		b2	=	a2
Β	b3	b7	b8	-		b3	=	a3
Β	b4	b9	b10	-		b4	=	a4
Β	b5	b11	b12	-		b5	=	a5
Β	b6	b13	b14	-		b6	=	a6
B	b7	b15	b16	-		b7	=	a7
B	b8	b17	b18	-		b8	=	a8
1	b9	b19	b20	-		b9	=	a9
0	b10	b21	b22	-		b10	=	a10
B	b11	b23	b24	-		b11	=	a11
1	b12	b25	b26	-		b12	=	a12
1	b13	b27	b28	-		b13	=	a13
0	b14	b29	b30	-		b14	=	a14
1	b15	-	-	b31		b15	=	a15
0	b16	-	-	b32		b16	=	a16
1	b17	-	-	b33		b17	=	a17
0	b18	-	-	b34		b18	=	a18
1	b19	-	-	B35		b19	=	a19
0	b20	-	-	B35		b20	=	a20
0	b21	-	-	b36		b21	=	a21
1	b22	-	-	b35		b22	=	a22
1	b23	-	-	b37		b23	=	a23
0	b24	-	-	b38		b24	=	a24
0	b25	-	-	B39		b25	=	a25
1	b26	-	-	B36		b26	=	a26
1	b27	-	-	B35		b27	=	a27
0	b28	-	-	B36		b28	=	a28
1	b29	-	-	B40		b29	=	a29
0	b30	-	-	B39		b30	=	a30
1	b31	-	-	B40		b31	=	a31
1	b32	-	-	B36		b32	=	a32
1	b33	-	-	B36		b33	=	a33
0	b34	-	-	B35		b34	=	a34
1	b35	-	-	b0'		b35	=	a35, a36, a38, a43, a50, a52
0	b36	-	-	b0’’		b36	=	a37, a 42, a44, a49
0	b37	-	-	b0'		b37	=	a39
1	b38	-	-	B0”		b38	=	a40
0	b39	-	-	b0'		b39	=	a41, a46, a 48, a51
1	b40	-	-	B0”		b40	=	a45, a47

3. Таблица 1.4 Упрощенная таблица переходов-выходов проектируемого автомата

y	a	0	1	
0	c0'	c1	c2	-		c0'	=	c0’
1	c0"	c1	c2	-		c0"	=	b0”
B	c1	c3	c4	-		c1	=	b1
B	c2	c5	c6	-		c2	=	b2
B	c3	c7	c8	-		c3	=	b3
B	c4	c9	c10	-		c4	=	b4
B	c5	c11	c12	-		c5	=	b5
B	c6	c13	c14	-		c6	=	b6
B	c7	c15	c16	-		c7	=	b7
B	c8	c17	c18	-		c8	=	b8
1	c9	c19	c20	-		c9	=	b9
0	c10	c21	c22	-		c10	=	b10
B	c11	c23	c24	-		c11	=	b11
1	c12	c25	c26	-		c12	=	b12
1	c13	c27	c28	-		c13	=	b13
0	c14	c29	c30	-		c14	=	b14
1	c15	-	-	C0”		c15	=	b15
0	c16	-	-	C0’		c16	=	b16
0	c17	-	-	C0”		c17	=	b17
1	c18	-	-	c0’		c18	=	b18
1	c19	-	-	C0”		c19	=	b19, b22, b27
1	c20	-	-	C0”		c20	=	b20, b34
0	c21	-	-	C0”		c21	=	b21, b28
0	c22	-	-	C0’		c22	=	b23
1	c23	-	-	C0’		c23	=	b24
0	c24	-	-	C0’		c24	=	b25, b30
0	c25	-	-	C0”		c25	=	b26, b32, b33
1	c26	-	-	C0”		c26	=	b29, b 31
1	c27	-	-	c0’		c27	=	b35, b38
0	c28	-	-	C0”		c28	=	b36
0	c29	-	-	c0’		c29	=	b37, b39
1	c30	-	-	c0”		c30	=	b40