Теория автоматов

Содержание

1. Задание на курсовой проект 3
2. Минимизация абстрактного автомата Мили 4
3. Синтез схемы конечного автомата 6
4. Схема автомата на D-триггерах 9

Список литературы 10

 

1. Задание на курсовой проект

Абстрактный автомат Мили задан таблицей переходов/выходов:

x(t)	s(t)
	s1	s2	s3	s4	s5	s6	s7	s8
x1	S4/y1	S8/y1	S8/y1	S3/y3	S7/y1	S1/y3	S3/y3	S6/y1
х2	S6/y2	S7/y2	S4/y2	S1/y1	S6/y2	S8/y1	S5/y1	S2/y2
х3	S8/y3	S5/y3	S5/y3	S6/y2	S8/y3	S2/y2	S6/y2	S4/y3

Таблица 1

 

Эта таблица определяет функцию переходов автомата s(t+1) = П [x(t), s(t)] и функцию выходов y(t) = B[x(t), y(t)]. Здесь s(t) - состояние, x(t) - входной и y(t) - выходной символ автомата в момент времени t.

Требуется:

а) минимизировать число состояний абстрактного автомата;

б) построить реакции исходного  и минимизированного автоматов  на входное воздействие x3x1x3x2x3x2x2x3, если начальное состояние автомата s[0] = s1;

в) синтезировать  автомат на элементах И-НЕ, ИЛИ-HE и D-триггерах.

 

 

 

 

 

 

 

3 

 

2. Минимизация абстрактного автомата  Мили

Таблица 2.1

 

x(t)	s(t)
	s1	s2	S3	s4	s5	s6	s7	s8
x1	S4/y1	S8/y1	S8/y1	S3/y3	S7/y1	S1/y3	S3/y3	S6/y1
х2	S6/y2	S7/y2	S4/y2	S1/y1	S6/y2	S8/y1	S5/y1	S2/y2
х3	S8/y3	S5/y3	S5/y3	S6/y2	S8/y3	S2/y2	S6/y2	S4/y3
	A1	A1	A1	A2	A1	A2	A2	A1

 

Разбиение на 1-классы эквивалентности осуществляется путём выявления одинаковых выходных символов автомата в столбцах таблицы 2.1, при этом получаем:

П1 = {А1,А2}

А1 = {s1,s2,s3,s5,s8}, А2 = {s4,s6,s7}

Строим таблицу 1-разбиения (табл. 2.2) и из неё находим разбиение  на 2- классы.

x(t)	s1	s2	s3	s4	s5	s6	s7	s8
x1	A2	A1	A1	A1	A2	A1	A1	A2
x2	A2	A2	A2	A1	A2	A1	A1	A1
x3	A1	A1	A1	A2	A1	A1	A2	A2
	B1	B2	B2	B3	B1	B4	B3	B5

Таблица 2.2

 

П2 = {В1,В2,ВЗ,В4,В5}

В1 = {s1,s5}, В2 = {s2,s3}, ВЗ = {s4,s7}, В4 = {s6}, В5 = {s8}

Строим таблицу 2-разбиения (табл. 2.3) и из неё находим разбиение  на 3- классы.

 

Таблица 2.3

x(t)	s1	s2	s3	s4	s5	s6	s7	s8
x1	В3	В5	В5	В2	В3	В1	В2	В4
х2	В4	В3	В3	В1	В4	В5	В1	В2
хЗ	В5	В1	В1	В4	В5	В2	В4	В3
	С1	С2	С2	СЗ	С1	С4	С3	С5

 

ПЗ = {С1,С2,СЗ,С4,С5}

C1 = В1, С2 = В2, С3 = ВЗ, С4 = В4, С5 = В5

 

 

Дальнейшее разбиение  невозможно. Таким образом, найдены - классы, которым соответствует  автомат Мили, описываемый таблицей переходов и выходов (табл. 2.4).

Таблица 2.4

x(t)	s(t)
	s1	s2	s3	s4	s5
x1	s3/y1	s5/y1	s2/y3	s1/y3	s4/y1
х2	s4/y2	s3/y2	s1/y1	s5/y1	s2/y2
хЗ	S5/y3	s1/y3	s4/y2	s2/y2	s3/y3

Построим реакции исходного  и оптимизированного автоматов  на входное воздействие x3x1x3x2x3x2x2x3, при начальном состоянии автомата s[0] = s1 (табл. 2.5).

                                                                                                                       Таблица 2.5

Вх.возд.	хЗ	x1	x3	x2	хЗ	x2	x2	хЗ
Исходный	y3	y1	у2	y2	у2	y1	y2	y3
Минимиз.	y3	y1	у2	y2	у2	y1	y2	y3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3. Синтез схемы конечного автомата

 

Выбор количества триггеров. Так как автомат имеет 5 состояний, то требуется q=]log25[=3 триггера.

Составление таблицы переходов. Составляем таблицу переходов (табл. З.1.), указывая текущие и будущие  состояния триггеров, а также  значения операторов перехода

Таблица 3.1

N	Sn	Sn+1	xi	x"	x'	yi	У"	У'	Q1	Q2	Q3	Q+1	Q+2	Q+3	G1	G2	G3
1	s1	s3	x1	0	0	y1	0	0	0	0	0	0	1	0	0	+	0
2	s1	s4	x2	0	1	y2	0	1	0	0	0	0	1	1	0	+	+
3	s1	s5	x3	1	0	y3	1	0	0	0	0	1	0	0	+	0	0
4	s2	s5	x1	0	0	y1	0	0	0	0	1	1	0	0	+	0	-
5	s2	s3	x2	0	1	y2	0	1	0	0	1	0	1	0	0	+	-
6	s2	s1	x3	1	0	y3	1	0	0	0	1	0	0	0	0	0	-
7	s3	s2	x1	0	0	y3	1	0	0	1	0	0	0	1	0	-	+
8	s3	s1	x2	0	1	y1	0	0	0	1	0	0	0	0	0	-	0
9	s3	s4	x3	1	0	y2	0	1	0	1	0	0	1	1	0	1	+
10	s4	s1	x1	0	0	y3	1	0	0	1	1	0	0	0	0	-	-
11	s4	s5	x2	0	1	y1	0	0	0	1	1	1	0	0	+	-	-
12	s4	s2	x3	1	0	y2	0	1	0	1	1	0	0	1	0	-	1
13	s5	s4	x1	0	0	y1	0	0	1	0	0	0	1	1	-	+	+
14	s5	s2	x2	0	1	y2	0	1	1	0	0	0	0	1	-	0	+
15	s5	s3	x3	1	0	y3	1	0	1	0	0	0	1	0	-	+	0

Таблицы кодирования входных, выходных и внутренних состояний автомата

 

Таблица 3.2 Таблица 3.3 Таблица 3.4

S	Q1	Q2	Q3
s1	0	0	0
s2	0	0	1
s3	0	1	0
s4	0	1	1
s5	1	0	0

y	y"	y'
y1	0	0
y2	0	1
yЗ	1	0

x	x"	x'
x1	0	0
x2	0	1
xЗ	1	0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Карты Карно для выходных функций

 

                                                      Таблица 3.5

x"x'\Q1Q2Q3	000	001	011	010	110	111	101	100
00	0	0	1	1	X	X	X	1
01	0	0	0	0	X	X	X	0
11	X	X	X	X	X	X	X	X
10	1	1	0	0	X	X	X	0

 

                                                                                                       Таблица 3.6

x"x'\Q1Q2Q3	000	001	011	010	110	111	101	100
00	0	0	0	0	X	X	X	0
01	1	1	0	0	X	X	X	0
11	X	X	X	X	X	X	X	X
10	0	0	1	1	X	X	X	1

 

 

 

Функция возбуждения D-триггера определяется выражением:

D = U{+,1,()}

 

Карты Карно функций возбуждения триггеров

                                                          Таблица 3.7

x"x'\Q1Q2Q3	000	001	011	010	110	111	101	100
00	0	+	0	0	X	X	X	-
01	0	0	+	0	X	X	X	-
11	X	X	X	X	X	X	X	X
10	+	0	0	0	X	X	X	-