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

ПЕРВОЕ ВЫСШЕЕ ТЕХНИЧЕСКОЕ УЧЕБНОЕ  ЗАВЕДЕНИЕ РОССИИ

МИНИСТЕРСТВО ОБРАЗОВАНИЯ  И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

федеральное государственное бюджетное  образовательное учреждение высшего  профессионального образования

«НАЦИОНАЛЬНЫЙ МИНЕРАЛЬНО-СЫРЬЕВОЙ УНИВЕРСИТЕТ  «ГОРНЫЙ»

 

Факультет приборостроения, информационных и  электронных систем

 

Кафедра  информационных систем и вычислительной техники

 

 

 

 

 

 

 КУРСОВОЙ ПРОЕКТ

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Специальность:230101.65

Студент:  Мурашкевич А.А.

Шифр: 9401020019

 

 

 

 

Санкт-Петербург

2012

 

Содержание

 

 

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

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

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

Приложение……………………………………………………………………11

Список используемой литературы……………………………………………12 
 
Задание на курсовой проект

 

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

Таблица №1

X(t)	S(t)
	S1	S2	S3	S4	S5	S6	S7	S8
X1	S4/Y1	S3/Y1	S8/Y3	S2/Y3	S1/Y3	S2/Y3	S6/Y1	S7/Y3
X2	S5/Y2	S4/Y2	S4/Y1	S1/Y1	S3/Y1	S7/Y1	S5/Y2	S3/Y1
X3	S2/Y3	S8/Y3	S1/Y2	S3/Y2	S6/Y2	S3/Y2	S2/Y3	S6/Y2

                 

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

 y(t) –выходной символ автомата в момент времени t.

Требуется:

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

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

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

Г) разобрать программу, моделирующую работу структурного автомата.

 

Часть 1

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

1. Выявляем тождественное состояние автомата

Таблица 2

X(t)	S(t)
	S1	S2	S3	S4	S5	S6	S7	S8
X1	S4/Y1	S3/Y1	S8/Y3	S2/Y3	S1/Y3	S2/Y3	S6/Y1	S7/Y3
X2	S5/Y2	S4/Y2	S2/Y1	S1/Y1	S3/Y1	S7/Y1	S5/Y2	S3/Y1
X3	S2/Y3	S8/Y3	S1/Y2	S3/Y2	S6/Y2	S3/Y2	S2/Y3	S6/Y2

                    А2             А2             А1            А1             А1            А1            А2             А1

2. Разбиваем на классы эквивалентности:

П1 = (А1;А2)

А1 = (s3, s4, s5, s6, s8)

A2 = (s1, s2, s7)

Находим столбцы, имеющие одинаковые значения выходных сигналов и строим модифицированную таблицу переходов:

Таблица 3

X(t)	S(t)
	S1	S2	S3	S4	S5	S6	S7	S8
X1	А1	А1	А1	А2	А2	А2	А1	А2
X2	А1	А1	А2	А2	А1	А2	А1	А1
X3	А2	А1	А2	А1	А1	А1	А2	А1

                     В1             В2             В3             В4             В5             В4             В1            В5

П2=(В1, В2, В3, В4, В5)

В1=(s1, s7); B2=(s2); B3 =(s3); B4 = (s4, s6); B5 = (s5, s8);

 

 

 

 

 

Таблица 4

X(t)	S(t)
	S1	S2	S3	S4	S5	S6	S7	S8
X1	В4	В3	В5	В2	В1	В2	В4	В1
X2	В5	В4	В2	В1	В3	В1	В5	В3
X3	В2	В5	В1	В3	В4	В3	В2	В4

                 С1             С2            С3              С4             С5            С4              С1             С5

 

П3 =(С1, С2, С3, С4, С5)

С1=(s1, s7); С2=(s2); С3 =(s3); С4 = (s4, s6); С5 = (s5, s8);

В1=С1, В2=С2, В3=С3, В4=С4, В5=С5;

 

Два класса совпало, пришли к бесконечному классу эквивалентности. Оставляем  в каждом классе эквивалентности  по 1 состоянию из представителей. Удаляем  в исходной таблице столбцы, соответствующие  лишним состояниям, переименовываем  в оставшихся столбцах удаленные  состояния именами представителей и получаем таблицу переходов  минимизированного автомата.

 

Таблица 5

X(t)	S(t)
	S1	S2	S3	S4	S5
X1	S4/Y1	S3/Y1	S5/Y3	S2/Y3	S1/Y3
X2	S5/Y2	S4/Y2	S2/Y1	S1/Y1	S3/Y1
X3	S2/Y3	S5/Y3	S1/Y2	S3/Y2	S4/Y2

 

3. Составим таблицу реакций исходного и минимизированного автоматов:

 

 

 

Таблица 6

Входное действие	Х3	Х2	Х3	Х1	Х3	Х1	Х1	Х3
Реакция исх. автомата	Y3	Y2	Y2	Y3	Y2	Y3	Y1	Y2
Реакция мин. автомата	Y3	Y2	Y2	Y3	Y2	Y3	Y1	Y2

 

 

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

Абстрактный синтез

1. Выбор количества триггеров. Так как автомат имеет 5 состояний, то требуется 3 триггера.
2. Кодирование внутренних состояний входных, выходных сигналов (кодирование произвольное):

X	x’’	x’		Y	y’’	y’		S	Q1	Q2	Q3
x1	0	0		y1	1	0		s1	0	0	0
x2	0	1		y2	1	1		s2	0	0	1
x3	1	1		y3	0	0		s3	0	1	0
								s4	0	1	1
								s5	1	0	0

На основании графа переходов  составляем таблицу переходов, указывая текущее и будущие состояние  триггеров, а также значения операторов перехода:

 

			Входной			Выходной			K(Sn)			K(Sn+1)			Б
№ п/п	Sn	Sn+1	Xi	X’	X”	Yi	Y	Y”	Q1	Q2	Q3	Q1	Q2	Q3	G1	G2	G3
1	s1	s4	x1	0	0	y2	1	1	0	0	0	0	1	1	0	+	+
2	s1	s5	x2	0	1	y1	1	0	0	0	0	1	0	0	+	0	0
3	s1	s2	x3	1	1	y3	0	0	0	0	0	0	0	1	0	0	+
4	s2	s3	x1	0	0	y2	1	1	0	0	1	0	1	0	0	+	-
5	s2	s4	x2	0	1	y1	1	0	0	0	1	0	1	1	0	+	1
6	s2	s5	x3	1	1	y3	0	0	0	0	1	1	0	0	+	0	-
7	s3	s5	x1	0	0	y2	1	1	0	1	0	1	0	0	+	-	0
8	s3	s2	x2	0	1	y1	1	0	0	1	0	0	0	1	0	-	+
9	s3	s1	x3	1	1	y3	0	0	0	1	0	0	0	0	0	-	0
10	s4	s2	x1	0	0	y3	0	0	0	1	1	0	0	1	0	-	1
11	s4	s1	x2	0	1	y2	1	1	0	1	1	0	0	0	0	-	-
12	s4	s3	x3	1	1	y1	1	0	0	1	1	0	1	0	0	1	-
13	s5	s1	x1	0	0	y3	0	0	1	0	0	0	0	0	-	0	0
14	s5	s3	x2	0	1	y2	1	1	1	0	0	0	1	0	-	+	0
15	s5	s4	x3	1	1	y1	1	0	1	0	0	0	1	1	-	+	+

3. Составление общих карт Карно

Так как автомат  содержит 3 триггера, то составляем три  обобщенные карты Карно и 2 карты  Карно для получения логического  выражения для функции выхода.

Составим 3 карты  Карно операторов перехода:

А) для G1

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	0	+	0	0	X	X	X	-
10	X	X	X	X	X	X	X	X

 

G1=

 

Б) для G2

X’ X”	Q1Q2Q3
	000	001	011	010	110	111	101	100
00	+	+	-	-	X	X	X	0
01	0	+	-	-	X	X	X	+
11	0	0	1	-	X	X	X	+
10	X	X	X	X	X	X	X	X