ДМ Практикум

	0	1	2	1			2 1 1 0
	1	0	1	0				1 0 1				0
а)						;	б)							;
	2	1	0	1				1 1 0				0
	1	0	1
				2			0 0 0 2
	0	1	2	0			0		2	0 0
	1	0	0	0				2	0	0		0
в)						;	г)						.
	2	0	0	2				0	0	0		2
	0	0	2						0	2 0
				0			0
											∞			5	1	1
8.20 Граф задан матрицей весов W (G) =												5		∞	4	∞
												1		4	∞	.
																1
														∞	1
											1					∞

Вес его минимального остова равен…

а) 5;

б) 4;

в) 7;

г) 6.

8.21 Три шага алгоритма Дейкстры приведены в таблице:

v*, d (v *), p (v *)	d (v1 )	d (v2 )	d (v3 )	d (v4 )	d (v5 )	d (v6 )	d (v7 )	d (v8 )
v1,0,	–	4	∞	∞	∞	1	2	6
v6 ,1,1	–	4	∞	4	5	–	2	6
v7 , 2,1	–	3	∞	4	5	–	–	6

Ведущая вершина на четвертом шаге…

а) v7 ; б) v2 ; в) v3 ;

г) v4 .

8.22 Три шага алгоритма Дейкстры приведены в таблице:

81

v*, d (v *), p (v *)	d (v1 )	d (v2 )	d (v3 )	d (v4 )	d (v5 )	d (v6 )	d (v7 )	d (v8 )
v1,0,	–	4	∞	2	∞	1	∞	∞
v5 ,1,1	–	4	6	2	5	–	∞	2
v4 , 2,1	–	4	3	–	5	–	6	2

Расстояние от вершины v1 до вершины v8 равно…

а) 1;

б) 2;

в) 3;

г) 4.

8.23Хроматическое число графа, изображенного на рисунке 8.3, равно…

а) 1;

б) 2;

в) 3;

г) 4.

Рисунок 8.3

8.24Хроматическое число графа, изображенного на рисунке 8.4, равно…

а) 1;

б) 2;

в) 3;

г) 4.

Рисунок 8.4

82

Глава IX. Конечные детерминированные автоматы

Конечным детерминированным автоматом (к.д.а.) называется пятерка

X ,Y , S,λ,δ	, где X = {x1, x2 ,...xn} - входной алфавит, Y = {y1, y2 ,...ym} - алфа-
вит выхода,	S = {s0 , s1, s2 ,...sk } - алфавит состояний с выделенным начальным

состоянием s0 , δ : X × S → S - функция переходов, λ : X × S → Y - функция вы- ходов. Работа автомата осуществляется в дискретные такты времени t = 1,2,3... .

Задается автомат с помощью таблицы переходов-выходов (рисунок 9.1) или

диаграммы Мура (рисунок 9.2).

Рисунок 9.1

Рисунок 9.2

Реализация к.д.а. осуществляется с помощью канонической таблицы

	λ	(	)
y (t) =			x (t),s (t) ;
и канонических уравнений: s (t + 1) = δ (x (t),s (t)); t = 1,2,3... .
s (1) = s0.

Для этого элементы X ,

Y и S кодируются:

x

= (x1

, x

2

,...xk ) ,

y

s

= ( y1

, y

2

,...yl ) ,

s

= (s1, s2

,...sm ) .

j

j

j

j

s

s

s

i

i i

i

Кодовые слова следует выбирать минимально возможной длины, началь- ное состояние кодируется словом (00…0).

83

Функциональным элементом называется устройство, вычисляющее эле- ментарную функцию. Элемент, способный удержать единицу информации в те- чении одного такта, называется единичной задержкой или триггером. Зная ка- нонические уравнения к.д.а. можно построить схему логического устройства, которое его реализует (рисунок 9.3). Для построения схемы используем элемент единичной задержки и элементы, порожденные функциями &, ,¬ (рисунок 9.4). Память устройства содержит в себе необходимое количество элементов задержки.

Рисунок 9.3

Рисунок 9.4

Минимизированный к.д.а. – это автомат, реализующий ту же функцию, что исходный, но с минимальным числом состояний. Минимизация автомата проходит следующим образом:

Шаг 1. Разбиваем состояния автомата на классы эквивалентности «по выходам». При этом в одном классе оказываются состояния, которые одинаково реагируют на входные символы на выходе: si s j , если

λ(x, si ) = λ(x, s j ) x X .

Шаг 2. Полученные на предыдущем шаге классы разбиваем «по перехо- дам». При этом эквивалентными считаем состояния, которые одинаково реагируют на входные символы при переходе, т.е. попадают в один и тот же класс эквивалентности, построенный ранее: si s j , если

δ(x, si ) δ(x, s j ) x X . Таким образом происходит «раздробление» уже

84

существующих классов. Возвращаемся на начало шага 2, и повторяем процесс до тех пор, пока количество классов не перестанет увеличивать- ся.

Пример 9.1.* Рассмотрим конечный автомат, описывающий поведение отца, имеющего сына – школьника. Сын приносит из школы двойки, тройки, четверки и пятерки, т. е. входным алфавитом конечного автомата будем считать множество

X = {2,3, 4,5}.

Реакция отца может быть следующая: Н –« не реагирует»; Р-«ругает»; Х – «хвалит»; У -«утешает», т. е. выходным алфавитом будем считать множество

Y = {Н, Р, Х ,У}.

Реакция отца зависит не только от того, какова текущая оценка, но и от того, какова была предыдущая, т. е. потребуются следующие состояния автома-

та:		s1 - «начальное состояние»;
		s2	- «предыдущая оценка –					двойка»;
		s3	- «предыдущая оценка –					тройка»;
		s4	- «предыдущая оценка –					четверка»;
		s5	- «предыдущая оценка –					пятерка».
Поведение родителя может быть, например, таким:
	S\X	2		3	4	5
	s1	s2 /Р		s3 /Н	s4 /Н	s5 /Х
	s2	s2 /Р		s3 /Р	s4 /Х	s5 /Х
	s3	s2 /Р		s3 /Н	s4 /Н	s5 /Х
	s4	s2 /У		s3 /Н	s4 /Н	s5 /Х
	s5	s2 /У		s3 /У	s4 /Н	s5 /Х
Состояния
	s1 и s3 эквивалентны, данный к.д.а. можно минимизировать,
приняв за начальное состояние s3					(отметим этот факт символом *):
	S\X	2		3	4	5
	s2	s2 /Р		s3 /Р	s4 /Х	s5 /Х
	s3 *	s2 /Р		s3 /Н	s4 /Н	s5 /Х
	s4	s2 /У		s3 /Н	s4 /Н	s5 /Х
	s5	s2 /У		s3 /У	s4 /Н	s5 /Х

85

Из примера следует, что решив некоторые технические вопросы, воспи- тательный процесс можно автоматизировать.

Конечные автоматы могут рассматриваться не только как преобразовате- ли информации, реагирующие на входные сигналы, но и как распознаватели последовательностей входных сигналов. Конечное множество входных сигна- лов называется словарем V, элементы словаря – символами, последовательно- сти символов словаря – предложениями или цепочками. Множество предложе- ний (конечной длины) над словарем V называется языком LV . Любой конечный механизм задания языка называется грамматикой. Роль распознающей (за- дающей критерий принадлежности произвольной последовательности симво- лов данному языку) грамматики может выполнять конечный автомат без выхо- да. Язык, для которого существует распознающий его конечный автомат, назы-

вается автоматным языком.

Конечным детерминированным автоматом - распознавателем называ-

ется четверка X , S,δ , F , где X = {x1, x2 ,...xn} - входной алфавит,

S = {s0 , s1, s2 ,...sk } - алфавит состояний с выделенным начальным состоянием s0 ,

δ : X × S → S - функция переходов;		F S - множество заключительных со-
стояний.
	Пример 9.2. Построить к.д.а. –	распознаватель для языка LV = {ab,ccc}
над словарем V = {a,b,c} .
	Конечный автомат будет иметь 2 заключительных состояния (по числу

распознаваемых им цепочек) s2 и s5 . Зададим к.д.а диаграммой Мура (рисунок

9.5):

Рисунок 9.5

* Идея примера взята из книги Карпов Ю. Г. Теория автоматов. – СПб: Питер, 2003г.

86

А) Контрольные вопросы

9.1Дайте определение конечного детерминированного автомата. В чем со- стоит содержательный смысл состояний к.д.а.?

9.2Перечислите способы задания и способы реализации к.д.а..

9.3Является ли детерминированным автомат без выхода, изображенный на рисунке 9.6?

Рисунок 9.6

9.4Постройте детерминированный автомат, эквивалентный изображенному на рисунке 9.6.

9.5Опишите алгоритм минимизации к.д.а.

Б) Задачи и упражнения

9.6Постройте конечный автомат, т.е. определите множества S, X,Y и задай- те функции переходов и выходов (постройте таблицу и диаграмму Мура), для следующих функций:

а) y (t) = x (t −1) , y (1) = 0 ;

б) y (t) = x (t −2) , y (1) = 0, y (2) = 0 ;

в) y (t) = x (t −1) x (t) , y (1) = 1;

г) y (t) = x (t −2) x (t −1) , y (1) = y (2) = 1;

д) y (t) = x (t) x (t −1) … x (1) ;

е) y (t) = x (t) x (t −1) … x (1) ,

здесь x (t) ,y (t) B, B = {0,1}, t = 1,2, 3,…

87

9.7 Минимизируйте к.д.а., заданный таблицей переходов-выходов:

X	0	1		2
S1	S2	S5	1	S5
	1	0
S2	S6	S2		S5
	0	1	1
а)	S2	S2		S7
S3
	0	1	1
S4	S4	S3		S1
	1	0	1
S5	S2	S5		S5
	1	0	1
S6	S2	S6		S5
	0	1	1
S7	S6	S6		S3
	0	1	1

X	0		1	2
1 S1	0 S4	0	S6	S1
0S2	0S2	1	S2	S6
б)
1 S3	0 S4	0	S2	S3
S4	S4		S3	S3
1	0	0
S5	S6		S6	S5
0	0	1
S6	S5		S6	S2
0	0	1
S7	S5		S6	S2
0	0	1

9.8Постройте канонические уравнения для к.д.а. из задачи 9.6. а)– е).

9.9Постройте схему из функциональных элементов для конечного автомата с памятью, описываемого следующими каноническими уравнениями:

									1										2		(t) x(t),
		y(t) = s								(t) s
		(t +1) = s																(									)
s														(t)					x(t) s								(t) ,
	1											2														1
а)
2													1	( )(												2	( ))	,
		(		)																	( )
s			t +1			= s t													x t						s t
				1												2
						( )												( )
				s							= s
						1												1					= 0,
			1								(t) x(t),
				(t) = s
		y
		y2		t	= s								t					t					,
											(			)	x					)
б)				( )														(
															x t									,
s t +1 = s t
	(			)							( )									( )
					( )
				s 1					= 0;

здесь x (t),y (t) B, B = {0,1}, t = 1,2, 3,…

9.10Для функций из задачи 9.6 а)– е) постройте схемы устройств, реализующих эти функции, используя элемент единичной задержки и элементы, поро- жденные функциями &, ,¬.

9.11Постройте конечный автомат, минимизируйте его, постройте канониче-

скую таблицу, канонические уравнения. Постройте схему устройства,

88

реализующего данную функцию, используя элемент единичной задержки и элементы, порожденные функциями &, ,¬.

а)

б)

в)

г)

д)

е)

				1, t ≥ 1,
y (2t −1) = x (2t −1)
y (2t) = x (2t) x (2t −1), t ≥ 1;
	= x (2t −1)	1, t ≥ 1,
y (2t −1)
		−1), t ≥ 1;
y (2t) = x (2t) x (2t

y (t) = x2 (t −1) → x1 (t), t ≥ 2,

y (1) = 1;

y (t) = x1 (t −1) x2 (t)x1(t), t ≥ 2,

y (1) = 1;

		(t) x2	(t),
y (t) = x	1

y (1) = 0;

y (t) = x1 (t −1) x2 (t −2), t ≥ 2,

y (1) = 1, y (2) = 1;

здесь x (t),y (t) B, B = {0,1}, t = 1,2, 3,…

9.12По схеме автомата (рисунок 9.7) постройте канонические уравнения, ка- ноническую таблицу, таблицу переходов-выходов и диаграмму Мура.

9.13Постройте конечный автомат без выхода с входным алфавитом {a,b} , воспринимающий те и только те входные слова, в которых за каждой бу- квой a следует буква b .

9.14Постройте конечный автомат без выхода с входным алфавитом {a,b} , воспринимающий те и только те слова, которые содержат подслово aba .

9.15Постройте конечный автомат без выхода с входным алфавитом {a,b,c} , воспринимающий те и только те слова, которые содержат одну букву a и одну букву b .

89

Рисунок 9.7

9.16Постройте конечный автомат без выхода с входным алфавитом {a,b,c} , воспринимающий те и только те слова, в которых первая и последняя бу- ква совпадают.

В) Тестовые задания (укажите единственный верный ответ)

9.17К.д.а. называется инициальным, если…

а) в нем выделено начальное состояние;

б) входной алфавит состоит из одного элемента;

в) алфавит состояний состоит из одного элемента;

г) функция выходов не зависит от элементов входного алфавита.

9.18Логический к.д.а., заданный системой канонических уравнений

y(t) = x(t),

+ =

s(t 1) s(t), …

s(1) = 0.

а) реализует задержку входного сигнала на один такт;

б) выдает значение входного сигнала без каких-либо преобразований;

в) реализует функцию x(t −1) & x(t) , y(1) = 0 ;

г) реализует функцию x(1) & x(t) ;

9.19К.д.а., заданный диаграммой Мура (рисунок 9.8), преобразует входное слово 10011 в выходное слово…

90