502_KHramova_T._V._Diskretnaja_matematika_proektirovanie_konechnykh_avtomatov_v_primerakh_i_zadachakh_

Рисунок 17.

Следуя диаграмме Мура, составим таблицу переходов-выходов:

	S	S1
	S0
		1
	S1	S2
		0
	S2	S3
		1
	S3	S4
		0
	S4	S5
		0
	S5	S0
		0

Поставим в соответствие состояниям последовательности «0» и «1»:

	S		S1S2S					3	000,		S	S1S		2S3		001,	S	S1S		2S		3	010,
0				0		0		0			1	1	1		1		2	2		2		2
	S		S1S2S					3	011,		S	S1S		2S3		100,	S	S1S		2S		3	101.
3				3		3	3				4	4		4	4		5	5	5		5
Составим каноническую таблицу:
	Si1(t)					Si2(t)				Si3(t)		y(t)			Si1(t 1)		Si2(t 1)					Si3(t 1)
			0				0			0		1				0		0					1
			0				0			1		0				0		1					0
			0				1			0		1				0		1					1
			0				1			1		0				1		0					0
			1				0			0		0				1		0					1
			1				0			1		0				0		0					0
			1				1			0		—				—		—					—
			1				1			1		—				—		—					—
Для y(t),		Si1(t 1)					и Si2(t 1) запишем и упростим СДНФ:
														41

y(t) Si1(t) Si2(t) Si3(t) Si1(t) Si2(t) Si3(t) Si1(t) Si3(t);

Si1(t 1) Si1(t) Si2(t) Si3(t) Si1(t) Si2(t) Si3(t);

Si2(t 1) Si1(t) Si2(t) Si3(t) Si1(t) Si2(t) Si3(t) Si1(t) Si2(t) Si3(t) Si2(t) Si3(t)

Значения Si3(t 1) можно выразить через отрицание значений Si3(t). Доопределим каноническую таблицу согласно (15):

	Si1(t)	Si2(t)		Si3(t)									y(t)					Si1(t 1)				Si2(t 1)										Si3(t 1)
	0	0		0							1								0					0								1
	0	0		1							0								0					1								0
	0	1		0							1								0					1								1
	0	1		1							0								1					0								0
	1	0		0							0								1					0								1
	1	0		1							0								0					0								0
	1	1		0							0								0					0								1
Запишем	1	1		1							0								0					0								0
	систему	канонических уравнений:
		y(t)
					S1(t)				S3(t),
					i						i
			1			1			(t) S						2	(t) S		3	1				2	(t) S				3	(t),
		S (t 1) S																	(t) S	(t) S												(15)
			i					i							i		i		i			i					i
		Si2(t 1) Si1(t) Si2(t) Si3(t) Si2(t) Si3(t) ,
			3				3			(t).
		Si (t 1) Si

Построениеавтоматов-распознавателей языка.

Во всех задачах построить автомат-распознаватель языка LV над алфавитом V

Пример 17. LV {ab,abab,...,ab...ab,...},V {a,b}

Решение. Построим диаграмму Мура (рисунок 18).

Рисунок 18.

42

Пример 18. LV {ab,cca},V {a,b,c}.

Решение. У автомата два заключительных состояния, по количеству распознаваемых слов. Построим диаграмму Мура (рисунок 19).

Рисунок 19.

Пример 19. LV { | содержит подслова ab или cca},V {a,b,c}.

Решение. Построим диаграмму Мура (рисунок 20).

Заключительные состояния можно отождествить:

Рисунок 20.

Следуя диаграмме Мура, составим таблицу переходов:

43

Состояния S1 и S3 идентичны, следовательно, их можно отождествить:

S	a	b
S0	S1	S4
S1	S4	S2
S2	S1	S4
S4	S4	S4

Состояния S0 и S2 идентичны, следовательно, их можно отождествить:

S	a	b
S1	S4	S2
*S2	S1	S4
S4	S4	S4

Поставим в соответствие состояниям и буквам алфавита входа последовательности «0» и «1»:

a 0,		b 1,			S	S1S2S3							000, S									S1S2S3								001, S					2	S1S		2S3		010,
					0		0	0				0							1			1					1	1								2		2	2
S	S1S2S3			011,		S	S1S2S3												100,				S S1S2S3 101.
3	3	3	3			4					4		4				4					5						5		5		5
Составим каноническую таблицу:
					Si1(t)					Si2(t)									x(t)				Si1(t 1)									Si2(t 1)
						0						0							0								0					1
						0						0							1								1					0
						0						1							0								1					0
						0						1							1								0					0
						1						0							0								0					1
						1						0							1								0					1
						1						1							0							—							—
Для Si1(t 1)						1						1							1							—							—
				и	Si2(t 1)					составим и упростим СДНФ и запишем систему
канонических уравнений:
					1																							2
									1								2							1
																															(t) x(t),
				Si (t 1) Si								(t) Si							(t) x(t) Si							(t) Si														(17)
				S2		(t 1) S					2(t)						x(t)			S1(t) S						2	(t) x(t).
					i					i											i				i
Доопределим каноническую таблицу согласно уравнениям (17):
					Si1(t)					Si2(t)									x(t)				Si1(t 1)									Si2(t 1)
						0						0							0								0					1
						0						0							1								1					0
						0						1							0								1					0
						0						1							1								0					0
						1						0							0								0					1
						1						0							1								0					1
						1						1							0								0					0
						1						1							1								0					0
																			44

Пример 20. LV { | содержит подслово aba},V {a,b}

Решение. У автомата одно заключительное состояние, в которое он переходит, распознав слово aba. Построим диаграмму Мура (рисунок 22).

Рисунок 22.

Следуя диаграмме Мура, составим таблицу переходов:

Поставим в соответствие состояниям и буквам алфавита входа последовательности

«0» и «1»:

	a 0,		b 1,				S S1S			2S	3	000, S			S1S2S3					001,
							0	0		0	0			1			1	1	1
	S S1S			2S	3 010,			S S1S				2S3		011,		S	S1S				2S		3	100,
2			2	2	2			3		3		3	3		4				4		4		4
Составим каноническую таблицу:
	Si1(t)		Si2(t)				Si3(t)		x(t)				Si1(t 1)			Si2(t 1)						Si3(t 1)
	0			0			0		0					0				0						1
	0			0			0		1					1				0						0
	0			0			1		0					0				0						1
	0			0			1		1					0				1						0
	0			1			0		0					0				1						1
	0			1			0		1					1				0						0
	0			1			1		0					0				1						1
	0			1			1		1					0				1						1
	1			0			0		0					0				0						1
	1			0			0		1					0				0						0
	1			0			1		0					—				—						—
	1			0			1		1					—				—						—
	1			1			0		0					—				—						—
	1			1			0		1					—				—						—
	1			1			1		0					—				—						—
	1			1			1		1					—				—						—

45

Для Si1(t 1) и Si2(t 1) запишем и упростим СДНФ. Значения Si3(t 1) можно выразить через СКНФ. Запишем систему канонических уравнений:

1

1

3

(t) x(t),

Si (t 1) Si

(t) Si

2

2

1

3

1

()t x()t

(t) x(t).

Si

(t 1) Si

(t) Si

Si

(t) Si

3

1

3

1

2

(t 1)

(t) S

(t) x(t)

(t) S

3

(t)

S

S

S (t) S

i

i

i

i

i

i

x()t Si1(t) Si2(t) Si3(t) x(t) .

Пример 21. LV { | четное число},V {0,1,2,...,9}.

Решение. Построим диаграмму Мура (рисунок 23).

Рисунок 23.

Пример 22. LV { | число, кратное 3},V {0,1,2,...,9}.

Решение. Число делится на 3, если сумма его цифр делится на 3. Автомат будет содержать состояния: «остаток от деления на 3 равен 0» (заключительное), «остаток от деления на 3 равен 1», «остаток от деления на 3 равен 2». Построим диаграмму Мура (рисунок 24).

Рисунок 24.

Пример 23. LV { | число, кратное 4},V {0,1,2,...,9}.

Решение. Число делится на 4, если две последние его цифры составляют число, которое делится на 4. Построим диаграмму Мура (рисунок 25).

46

Рисунок 25.

Задачидля самостоятельного решения

Построить конечный детерминированный автомат (определить алфавиты, построить таблицу и диаграмму Мура), построить каноническую таблицу,

канонические уравнения.

1) y t x t x 2 , t 2, y 1 1.

2) y t x t 1 x t , t 2, y 1 0.

3) y t x1 t 1 x2 t , t 2, y 1 1. 4) y t x t x 2 , t 2, y 1 1.

5)y 101101101...

6)y 100100100 .

Построить автомат — распознаватель языка LV :

7)LV { | число, кратное5},V {0,1,2,...,9}.

8)LV { | содержит подсловоaaba},V {a,b}.

9)LV {ba,cac,cca,a},V {a,b,c}.

СПИСОК ЛИТЕРАТУРЫ

[1]Бернштейн Т.В., Макаров Р.Н., Храмова Т.В. Дискретная математика: Учебное пособие. – Новосибирск: СибГУТИ, 2004. – 91с.

[2]Бернштейн Т.В., Храмова Т.В. Дискретная математика: Сборник задач. – Новосибирск: СибГУТИ, 2004. – 50с.

[3]Мальцев И.А. Дискретная математика. – Новосибирск: Изд-во Института математики, 2007. – 228 с.: ил.

[4]Бернштейн Т.В., Храмова Т.В. Практикум по дискретной математике.

– Новосибирск: СибГУТИ, 2011. – 131с.

47

Учебное издание

Храмова Татьяна Викторовна

Дискретная математика: проектирование

конечных автоматов в примерах и задачах

Учебное пособие

В авторской редакции

Подписано в печать 28.10.2014г.,

формат бумаги 60x84/16, отпечатано на ризографе, шрифт №10, изд. л. 2,8, заказ № 132, тираж 50. СибГУТИ

630102, Новосибирск, ул. Кирова, 86.