Построение реакций минимизированного автомата

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

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

Северо-Западный государственный заочный технический университет

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

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

Контрольная работа

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

Построение реакций минимизированного автомата

Студент: Корчагин Ю. И.

Преподаватель: Иванова И. В.

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



Содержание

Введение

1. Минимизация абстрактного автомата, заданного таблицей переходов/выходов

1.1 Минимизирование числа состояний абстрактного автомата

1.2 Построение реакций исходного автомата и минимизированного автомата на входное воздействие

1.3 Синтезирование автомата на элементах ИЛИ-НЕ и Т - триггерах и на элементах И-НЕ и JK - триггерах



Введение

Для формального описания электронных схем, которые делят на два типа в зависимости от того, каким образом выходной сигнал зависит от входного, используют соответствующий аппарат. Математический аппарат алгебры логики пригоден для анализа и синтеза схем без памяти, то есть таких схем, в которых совокупность выходных сигналов в любой момент времени представляет собой однозначную функцию входных сигналов в тот же момент времени. Реализуемый в этих схемах способ обработки информации называется комбинационным, так как результат на выходе зависит только от комбинации входных сигналов. Схемы с памятью, алгоритм работы которых зависит от времени, описываются с помощью математического аппарата теории конечных автоматов. Понятие цифрового автомата, как средства для представления и обработки любых видов информации, является одним из основных в информатике. Конечными автоматами являются как отдельные узлы ЭВМ, так и вся вычислительная машина. С появлением новых инструментальных средств и подходов в области программного обеспечения модель конечного автомата широко используется не только для описания функционирования устройств переработки дискретной информации, но и для описания поведения программных агентов, то есть положена в основу технической имитации интеллекта. Автомат в этом случае рассматривают как эквивалент некоторой абстрактной среды, переходящей из одного состояния в другое в результате целенаправленных действий когнитивных агентов. Использование аппарата теории автоматов для анализа и проектирования многоагетных систем, в первую очередь, связано с объектно-ориентированным подходом, который является в настоящее время одним из наиболее интенсивно развивающихся направлений теоретического и прикладного программирования.



1. Минимизация абстрактного автомата, заданного таблицей переходов/выходов

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

x(t)	S(t)
	S1	S2	S3	S4	S5	S6	S7	S8
x1	s4/y3	s8/y1	s5/y1	s6/y3	s8/y1	s5/y1	s4/y3	s1/y1
x2	s2/y2	s4/y3	s1/y3	s8/y2	s4/y3	s7/y3	s5/y2	s6/y3
x3	s3/y1	s1/y2	s8/y2	s2/y1	s7/y2	s8/y2	s3/y1	s4/y2

Эта таблица определяет функцию переходов автомата

s(t+1) = П[x(t),

s(t)] и функцию выходов

y(t) =B[x(t), y(t)].

Здесь s(t) - состояние, x(t) - входной и y(t) - выходной символ автомата в момент времени t.

Требуется:

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

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

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

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

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



1.1 Минимизирование числа состояний абстрактного автомата

x(t)	S(t)
	S1	S2	S3	S4	S5	S6	S7	S8
x1	s4/y3	s8/y1	s5/y1	s6/y3	s8/y1	s5/y1	s4/y3	s1/y1
x2	s2/y2	s4/y3	s1/y3	s8/y2	s4/y3	s7/y3	s5/y2	s6/y3
x3	s3/y1	s1/y2	s8/y2	s2/y1	s7/y2	s8/y2	s3/y1	s4/y2

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

П={В1, В2}, где

В1={s1, s4, s7},

В2={s2, s3, s5, s6, s8}.

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

x(t)	В1	В2
	s1	s4	s7	s2	s3	s5	s6	s8
x1	В1	В2	В1	В2	В2	В2	В2	В1
x2	В2	В2	В2	В1	В1	В1	В1	В2
x3	В2	В2	В2	В1	В2	В1	В2	В1

П={С1, С2, С3, С4, С5}, где

С1={s1,s7},

C2={s4},

C3={s2, s5},

C4={s3,s6},

C5={s8}.



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

x(t)	C1	C2	C3	C4	C5
	s1	s7	s4	s2	s5	s3	s6	s8
x1	C2	C2	C4	C5	C5	C3	C3	C1
x2	C3	C3	C5	C2	C2	C1	C1	C4
x3	C4	C4	C3	C1	C1	C5	C5	C2

П={D1, D2, D3, D4, D5}, где

D1={s1, s7},

D2={s4},

D3={s2, s5},

D4={s3, s6},

D5={s8}.

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

	s1	s4	s2	s3	s8
x1	s4/y3	s3/y3	s8/y1	s2/y1	s1/y1
x2	s2/y2	s8/y2	s4/y3	s1/y3	s3/y3
x3	s3/y1	s2/y1	s1/y2	s8/y2	s4/y2



1.2 Построение реакций исходного автомата и минимизированного автоматов на входное воздействие

Построим граф-схему автомата.

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

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

Входное воздействие	x3	x1	x2	x1	x2	x2	x1	x3
Не минимизированный	y1	y1	y3	y3	y3	y2	y1	y2
Минимизированный	y1	y1	y3	y3	y3	y2	y1	y2

1.3 Синтезирование автомата на элементах ИЛИ-НЕ и Т-триггерах и на элементах И-НЕ и JK-триггерах

абстрактный автомат кодирование сигнал

Кодирование внутренних состояний входных, выходных сигналов (кодирование произвольное):



Построение абстрактной и структурной таблицы.

№	sn	Sn+1	Входной	выходной	k(sn)	k(sn+1)	д
			xi	x'	x''	yi	y'	y''	Q1	Q2	Q3	Q1	Q2	Q3	V1	V2	V3
1	s1	s4	x1	0	0	y3	0	0	0	0	0	0	1	1	0	+	+
2	s1	s2	x2	0	1	y2	1	1	0	0	0	0	0	1	0	0	+
3	s1	s3	x3	1	1	y1	1	0	0	0	0	0	1	0	0	+	0
4	s2	s8	x1	0	0	y3	0	0	0	0	1	1	0	0	+	0	-
5	s2	s4	x2	0	1	y2	1	1	0	0	1	0	1	1	0	+	1
6	s2	s1	x3	1	1	y1	1	0	0	0	1	0	0	0	0	0	-
7	s3	s2	x1	0	0	y1	1	0	0	1	0	0	0	1	0	-	+
8	s3	s1	x2	0	1	y3	0	0	0	1	0	0	0	0	0	-	0
9	s3	s8	x3	1	1	y2	1	1	0	1	0	1	0	0	+	-	0
10	s4	s3	x1	0	0	y1	1	0	0	1	1	0	1	0	0	1	-
11	s4	s8	x2	0	1	y3	0	0	0	1	1	1	0	0	+	-	-
12	s4	s2	x3	1	1	y2	1	1	0	1	1	0	0	1	0	-	1
13	s8	s1	x1	0	0	y1	1	0	1	0	0	0	0	0	-	0	0
14	s8	s3	x2	0	1	y3	0	0	1	0	0	0	1	0	-	+	0
15	s8	s4	x3	1	1	y2	1	1	1	0	0	0	1	1	-	+	+

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

Т-триггер. Т={+, -, (Ш)}

	Q1Q2Q3
x'x''	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



Для V2.

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

Для V3.

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

JK-триггер. J={+, (-), (1), (Ш)}; K={-, (+), (0), (Ш)}



Для V1, J-триггер

	Q1Q2Q3
x'x''	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

Для V1, K-триггер.

	Q1Q2Q3
x'x''	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

Для V2, J-триггер.

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



Для V2, К-триггер.

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

Для V3, J-триггер.

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

Для V3, К-триггер.

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

Функции выходов.

Для y', объединение по 1.

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

Для y', объединение по 0.

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



Для y'', объединение по 1.

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

	Q1Q2Q3
x'x''	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	0	0	1	1	x	x	x	1
10	x	x	x	x	x	x	x	x

На основании полученных выше выражений составляем схемы абстрактного автомата. На количество входов логических элементов ограничения не налагаем.



Рисунок 2 Схемная реализация автомата на элементах ИЛИ-НЕ и Т-триггерах



Рисунок 3 Схемная реализация автомата на элементах И-НЕ и JK-триггерах

Размещено на Allbest.ru