TVPS_posobie_13_06_2013

Таблица 12

Задание Д—, Д+,

Вариант		Д—			Д+			Вариант		Д—			Д+			Вариант		Д—			Д+
1		100000			110000		101100	2		101000			100100		100001	3		100000			111000		100011
		010100			000101					000001			001001					011000			010000
		101000			001010					101001			010010					100010			000100
		100011			000000					110011			000000					000301			001001
4	21000			01000			100000	5	100000			100010			100100	6	100000			110000			100020
	00011			00111					011000			100010					110000			001011
	00100			10000					100010			001101					000010			000011
	00011			11000					100101			000000					011200			000100
7		100000			110100		110000	8		100000			100100		100001	9		100000			110010		100001
		110000			001002					110100			000001					011000			000010
		100000			001000					000010			001000					100000			001111
		001100			001010					000002			001000					100101			000000
10	100000			111000			100000	11	100000			100100			100000	12	100000			100101			130000
	110000			000001					100100			011000					100100			010000
	000010			000111					001100			000010					000201			000010
	001011			000000					110010			000002					020110			001001
13		100000			101100		010001	14		100000			100101		001000	15		100000			110100		200001
		001000			010010					100100			010000					101000			001112
		100001			000101					000201			000010					010100			001000
		100001			000000					020010			001001					101000			000000
16	100000			110000			100011	17	200000			200110			100010	18	100000			110010			100000
	110000			000010					200000			010000					110000			001003
	000011			000001					010100			001000					001010			001100
	100110			001100					010101			001010					101000			000000
19		100000			101100		100000	20		110000			000100		100000	21		100000			101100		100100
		100100			010001					001000			111000					001210			000010
		000011			001000					001000			000101					101000			010001
		020010			000010					000202			000010					110001			000000
22	100000			110001			100010	23	010000			110010			100000	24	100000			111000			100001
	010000			001000					100010			101000					001000			000100
	101001			000010					011000			000100					101000			000101
	002100			000100					000201			000010					000202			000011
25		100000			111000		100100	26		100000			111000		100010	27		100000			111000		100000
		101000			000002					110000			000011					110000			000001
		000001			001110					001000			000101					100011			000010
		100001			000000					000012			000010					000020			000110
28	21000			01000			100000	29	100000			100010			100100	30	100000			110000			100020
	00011			00111					011000			100010					110000			001011
	00100			10000					100010			001101					000010			000011
	00011			11000					100101			000000					011200			000100

141

Упражнение 8

Для сети С=(Н, Т, D+, D-) требуется: а) найти составную матрицу изменений D;

б) определить = ( k; tj); k=0, 1, 2; j=1, 2, 3, 4;

в) выполнить преобразование Хэка; г) исследовать свойства (активность, сохранение, безопасность) как

исходной сети, так и сети, полученной в результате преобразования Хэка; д) установить, является ли сеть автоматной, синхрографом, сетью со

свободным выбором, ответ пояснить.

Информация о матрицах D— и D+ содержится в табл. 13, o маркировках – в табл. 14.

									Таблица 13
			Описание матриц D— и D+
Вариант	D —		D +	Вариант	D —	D +	Вариант	D —	D +
1	00100		00110	2	00110	01100	3	10000	11000
	10010		10001		10100	01100		00110	00101
	01002		00100		02001	00100		01001	00020
	00110		01100		00010	00020		20001	01010
4	10010	10001		5	10010	10001	6	00011	01001
	10100	01020			01100	00021		00101	00101
	10002	00100			00012	01000		01000	10020
	01000	00110			10100	01100		20010	00100
7	01001		11000	8	01000	01010	9	01100	00010
	10010		10011		10020	00100		01011	01100
	00100		00200		00101	10000		10000	01001
	01020		00010		10010	02101		00200	10002
10	01020	01001		11	00110	00200	12	10001	10010
	10010	02001			01001	10110		01010	10000
	00100	10010			10010	01001		00102	01001
	10001	00100			10001	10010		10000	00210
13	00100		10102	14	10010	10010	15	01001	11000
	10010		02100		01200	00010		10010	01001
	01100		00010		00001	01100		20000	10100
	10002		01000		11010	20001		00101	00020
16	10011	00020		17	01001	11000	18	01100	00101
	20000	01010			00100	00101		20000	01000
	00100	00101			20000	01010		10001	00110
	01001	11000			10011	00020		00011	12000
19	01011		01100	20	00110	01100	21	20100	00100
	00200		10002		10100	10011		01000	10020
	00001		01001		02001	00100		00101	01001
	01100		00010		00010	00020		01001	01002

142

Окончание табл. 13

22	01001	01002		23	00100	10101	24	10010	10001
	10100	10010			10001	02000		01000	00110
	10100	00100			01001	00010		10001	00012
	00020	10001			10020	01001		20010	10000
25	10100		00100	26	00100	00110	27	01100	00010
	01001		00012		10011	02100		00010	01001
	20010		10000		10010	10001		10200	10002
	01000		11010		01002	00100		01011	01100
28	00100	00110		29	00110	01100	30	10000	11000
	10010	10001			10100	01100		00110	00101
	01002	00100			02001	00100		01001	00020
	00110	01100			00010	00020		20001	01010

Таблица 14

Описание матриц D— и D+

Вариант	0		1		2		Вариант	0		1		2		Вариант	0		1		2
1	01102		01012		11110		11	11001		10102		11110		21	01021		11020		11101
2	02110		01011		10111		12	10012		10102		11110		22	11020		00121		11101
3	21001		20101		01111		13	21100		90101		01111		23	11201		01210		11011
4	11020		10021		11101		14	01102		11002		11110		24	20101		20011		01111
5	11020		10120		11101		15	01201		01210		11011		25	20011		01111		21012
6	10102		11002		11110		16	21001		20101		01111		26	21100		20011		01111
7	01211		11200		11011		17	10120		01021		11101		27	21010		20110		01111
8	02110		02011		10111		18	10021		10120		11101		28	01102		01012		11110
9	21100		20101		01111		19	21010		20011		01111		29	11200		10210		11011
10	11020		00121		11101		20	11020		10120		11101		30	01201		01210		11011

Упражнение 9

Для сети Петри, полученной в упражнении 8:

1)установить, является ли сеть: общей без петель, ординарной, бесконфликтной, сетью со свободным выбором, автоматной, маркированным графом, устойчивой;

2)проверить, является ли сеть живой;

3)удалить петли;

4)удалить кратные дуги.

143

Вопросы для самоконтроля

1.В чем разница между множеством и комплектом?

2.Как интерпретируются переходы и позиции в сетях Петри?

3.Как можно задать сеть Петри?

4.Какими свойствами обладает граф сети Петри?

5.Что такое «маркировка» сети Петри?

6.При каких условиях переход в сети Петри может быть запущен?

7.Как изменится маркировка сети Петри в результате запуска разрешѐнного перехода?

8.Как описывается состояние сети Петри? Что такое пространство состояний сети Петри?

9.Какие две последовательности, описывают выполнение сети Петри?

10.Дайте определение термину «Непосредственно достижимая маркировка». Сравните его с определением достижимой маркировки.

11.Что такое множество достижимости сети Петри?

12.Какая сеть Петри называется безопасной?

13.Какая сеть Петри называется ограниченной?

14.Какая сеть Петри называется строго сохраняющей, а какая сохраняющей по отношению к вектору взвешивания?

15.Какие уровни активности перехода вы знаете? Какой переход называют пассивным?

16.Какой переход имеет уровень активности 1, 2, 3 и 4?

17.Как определяется уровень активности сети Петри?

18.Какой переход называется устойчивым? Какая сеть Петри называется устойчивой?

19.В каком случае сеть Петри обладает свойством параллелизма?

20.В каком случае сеть Петри обладает свойством конфликтности?

21.Какие задачи анализа сетей Петри Вы знаете?

22.Сформулируйте задачу достижимости для сети Петри.

23.Сформулируйте задачу покрываемости для сети Петри.

24.Какие методы анализа сетей Петри Вы знаете?

25.Что такое дерево достижимости?

144

26.Дайте определения терминов «граничная маркировка», «терминальная маркировка».

27.Назовите средства ограничения дерева достижимости до конечных размеров.

28.Опишите основные шаги алгоритма построения усечѐнного дерева достижимости.

29.Сформулируйте леммы 1, 2 и 3 для доказательства теоремы о конечности дерева достижимости сети Петри.

30.Сформулируйте теорему о конечности усеченного дерева достижимости сети Петри.

31.Как проверить свойства безопасности и ограниченности сети Петри на основе дерева достижимости?

32.Как решается задача сохранения для сети Петри на основе дерева достижимости?

33.Как решаются задача покрываемости и достижимости сети Петри на основе дерева достижимости?

34.Для каких сетей Петри нельзя в общем случае решить задачу покрываемости и достижимости на основе дерева достижимости?

35.Напишите фундаментально уравнение сетей Петри.

36.В чем состоит роль фундаментального уравнения?

37.Как решить задачу достижимости с помощью матричного подхода?

38.Как решить задачу сохранения с помощью матричного подхода?

39.Какое преобразование сети Петри называется LB-эквивалентным?

40.Как исключить петлю из сети Петри?

41.Какие сети Петри называются ординарными?

42.Какими свойствами обладают ординарные сети Петри?

43.Какая сеть Петри называется персистентной?

44.Сформулируйте теорему о тупиковой маркировке персистентной сети.

45.Дайте определение автоматных сетей Петри.

46.Какими свойствами обладают автоматные сети Петри?

47.Дайте определение сети Петри со свободным выбором.

48.Какие сети Петри называются маркированными графами?

145

49.Для чего используются модификации и расширения сетей Петри?

50.Какие модификации сетей Петри Вы знаете?

51.Какие расширения сетей Пери Вы знаете?

146

3.Конечные автоматы

В основу данного раздела положены материалы из книг В. Б. Кудрявцева «Введение в теорию автоматов» [4] и В. Е. Котова «Сети Петри» [3], дополненные и переработанные авторами.

3.1.Основные понятия теории конечных автоматов

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

Наиболее простой и тщательно разработанной моделью для таких систем и устройств является конечные автоматы. Теория конечных автоматов (КА) возникла в середине 20-х годов XX века. Сам термин «конечный автомат» был предложен Клини в 1951 году.

Автомат является математической абстракцией системы (машины, устройства) переработки информации или процесса переработки. Автомат имеет конечное число входов, воспринимающих дискретную информацию, т.е. информацию, изображаемую конечным числом символов из некоторого алфавита, и конечное число выходов для выдачи информации. Переработка информации осуществляется в дискретном времени, т.е. во времени, представленном в квантованной шкале. Процесс переработки может быть разбит на этапы, каждый из которых характеризуется некоторым состоянием, в котором находится автомат. Конечный автомат имеет конечное число состояний. Если автомат моделирует систему сложной структуры, то он может быть представлен как

147

совокупность взаимодействующих автоматов, моделирующих ее подсистемы (компоненты системы).

3.2.Различные подходы к определению понятия

«конечный автомат»

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

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

Структурный КА задается конечным множеством абстрактных КА, конечной схемой их соединения и описанием влияния частей схемы друг на друга.

Определение. КА есть пятерка М=(А, Q, B, , ), где

А={а1, …, аk} – конечное множество возможных входных сигналов (входной алфавит);

Q={q1,...,qr} – конечное множество возможных внутренних состояний (внутренний алфавит или алфавит состояний);

В={b1, …, bp} – конечное множество возможных выходных сигналов (выходной алфавит);

:Q А Q – функция переходов (следующего состояния);

:Q А В – функция выходов.

Определение. КА называется инициальным, если в нем выделено начальное состояние q Q, в противном случае КА называется неинициальным.

148

Закон функционирования автомата, описываемого моделью Мили (автомат первого рода или R-автомат) имеет вид:

q(t+1)= (q(t), a(t)); b(t)= (q(t), a(t)).

В случае, когда функция выходов не зависит от второго аргумента (от входного сигнала), автомат М называется

абстрактным конечным автоматом Мура.

Закон функционирования автомата Мура (автомат второго рода или S-автомат) имеет вид:

q(t+1)= (q(t), a(t)); b(t)= (q(t))).

3.3.Способы задания конечных автоматов

Матричный способ. Функции и задаются матрицами Cи С размерности k r, k=|А|, r=|Q|:

(c )ij= (qj, ai), (c )ij= (qj, ai).

Пример 54. Пусть А={0, 1, 2}; В={0, 1, 2}; |Q|=4.

Например, (c )24=1. Это означает, что при поступлении входного сигнала «1» (a2=1), автомат перейдет в состояние q1, при условии, что он находился до этого момента в состоянии q4.

Табличный способ. Строится таблица из k строк и r столбцов. На пересечении i-той строки и j-го столбца помещаются значения

(qj, ai), (qj, ai) (табл. 15).

149

Таблица 15

КА задан в виде таблицы

a	q	q1	q2	q3 q4

0q1, 0 q3, 1 q1, 0 q2, 1

1q2, 1 q1, 0 q3, 1 q1, 0

2q1, 2 q2, 2 q1, 2 q1, 2

Графический способ. Еще один способ задания КА – это конечный ориентированный мультипсевдограф (Рис. 94). Вершины графа соответствуют состояниям. Количество вершин в графе r=|Q|. Дуги имеют двойную пометку (ai, bj), где ai А, bj В. Такой граф называют диаграммой переходов, диаграммой состояний, диаграммой Мура, графом поведения автомата.

Для диаграммы переходов должны выполняться следующие условия корректности.

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

Условие непротиворечивости. Каждая буква из А встречается в качестве пометки только на одной дуге, выходящей из вершины qj

(Рис. 94).

	00		21
	q1	11	q2
10	21	01	10	11
					01
	q3	01	q4
	21		20

Рис. 94. Пример КА в виде диаграммы состояний

Замечание. В диаграмме Мура начальную вершину обозначают символом «*» или « ».

150