TVPS_posobie_13_06_2013

23.Две последовательности, описывающие выполнение сети Петри. Расширенная функция следующего состояния. Принцип монотонности.

24.Достижимая маркировка. Непосредственно достижимая маркировка. Множество достижимости сети Петри. Пример.

25.Сеть Петри как модельная интерпретация АП.

26.Свойства сетей Петри. Безопасность.

27.Свойства сетей Петри. Ограниченность.

28.Свойства сетей Петри. Сохранение.

29.Свойства сетей Петри. Активность.

30.Свойства сетей Петри. Асинхронность. Устойчивость. Параллелизм. Конфликтность.

31.Класс свободных языков сетей Петри.

32.Помеченные сети Петри. Пример.

33.Префиксный язык сети Петри. Свободный терминальный язык сети Петри. Терминальный язык сети Петри. Пример.

34.Три вида помечающих функций для сетей Петри.

35.Классы языков сетей Петри. Пример.

36.Стандартная форма помеченных сетей Петри (определение). Лемма о существовании стандартной формы для любой сети Петри. Следствие.

37.Сравнение классов языков сетей Петри.

38.Основные задачи анализа сетей Петри: задачи достижимости и покрываемости. Пример.

39.Основные задачи анализа сетей Петри: задачи эквивалентности.

40.Методы анализа сетей Петри: дерево достижимости. Пример. Граничная, терминальная, дублирующая, внутренняя вершины (маркировки).

41.Средства ограничения дерева достижимости до определенных (конечных) размеров.

42.Алгоритм построения дерева достижимости.

43.Лемма 1 для доказательства теоремы о конечности дерева достижимости сети Петри.

44.Лемма 2 для доказательства теоремы о конечности дерева достижимости сети Петри.

45.Лемма 3 для доказательства теоремы о конечности дерева достижимости сети Петри.

46.Терема о конечности дерева достижимости сети Петри.

191

47.Решение задачи безопасности и ограниченности сетей Петри на основе дерева достижимости.

48.Решение задачи сохранения сетей Петри на основе дерева достижимости.

49.Решение задачи покрываемости и достижимости сетей Петри на основе дерева достижимости. Проблемы, возникающие в случае наличия неограниченной позиции. Пример.

50.Анализ свойств сетей на основе использования матричного

подхода: матрицы D-, D+, пример построения матриц для сети Петри.

51.Составная матрица изменений (матрица инцидентности). Пример. Замечания по применению матричного подхода.

52.Получение фундаментального уравнения сети Петри.

53.Роль фундаментального уравнения. Утверждения 1, 2.

54.Решение задачи достижимости с помощью матричного подхода. Замечание. Пример.

55.Теорема о повторяющейся последовательности сети Петри. Стационарно повторяющаяся последовательность запусков. Пример.

56.Решение задачи сохранения с помощью матричного подхода. Пример.

57.LB-эквивалентные преобразования.

58.Теорема об исключении петли.

59.Ординарные сети Петри (определение). Преобразование произвольной сети Петри в ординарную посредством преобразования Xэка. Теорема о преобразовании Хэка.

60.Бесконфликтные сети Петри. Персистентные сети (определение, замечание).

61.Теорема о тупиковой маркировке персистентной сети.

62.Автоматные сети Петри. Свойства АСП.

63.Сети Петри со свободным выбором.

64.Маркированные графы (определение). Утверждения 1, 2.

65.Модификации сетей Петри: область ограничения, переход «исключающее или».

66.Модификации сетей Петри: переключатель.

67.Расширения сетей Петри: сети со сдерживающими дугами.

68.Расширения сетей Петри: сети с приоритетами.

69.Расширения сетей Петри: синхронные сети.

70.Расширения сетей Петри: раскрашенные сети.

192

71.Расширения сетей Петри: самомодифицирующиеся сети.

72.Моделирование сетью Петри простой вычислительной системы.

73.Сетевое моделирование программного обеспечения для ЭВМ.

Раздел 3: Конечные автоматы

74.Различные подходы к определению понятия «конечный автомат». Определение КА. Автомат Мили. Автомат Мура.

75.Способы задания конечных автоматов: матричный способ, графический способ.

76.Способы задания конечных автоматов: табличный способ, графический способ.

77.Основная модель конечного автомата.

78.Этапы решения задачи синтеза КА.

79.КА как преобразователь. Пример.

80.КА как распознаватель. Пример.

81.КА как перечислитель. Пример.

82.Задача диагностики для КА. Пример.

83.Эквивалентные состояния для двух автоматов. Эквивалентные автоматы. Минимальный автомат.

Задача минимизации КА (как 2 вопроса в 1 билете)

84.Этап нахождения эквивалентных состояний при минимизации КА (вопрос 1).

85.Этап построения минимального автомата при минимизации КА

(вопрос 2).

86.Грамматика. Класс рекурсивно перечислимых языков. Грамматика, порождающая контекстно-зависимый язык и контекстно-свободный язык. Соотношение классов контекстнозависимых и контекстно-свободных языков. Регулярный язык.

87.Регулярная грамматика. Пример. Переход от регулярной грамматики к КА.

88.Детерминированный КА. Пример. Расширенная функция переходов. Множество строк, принимаемых КА.

89.Преобразование КА, порождающего язык над алфавитом А, в

помеченную сеть без -переходов. 90. Теорема 1: а) La L0, б) La L.

193

91.Теорема 2 о существовании терминального языка, порождаемого помеченной сетью Петри и не являющегося контекстно-свободным.

92.Теорема 3 о существовании контекстно-свободного языка, не порождаемого ни одной помеченной сетью Петри.

93.Некоторые специальные классы КА: автономный КА, автоматчасы, переходная система.

94.Некоторые специальные классы КА: автомат без памяти, автомат без потери информации, связный КА, сильно связный КА, инициально связный КА.

95.Обобщения КА: автомат Тьюринга.

96.Обобщения КА: однородный автомат, счетчиковый автомат.

97.Обобщения КА: вероятностный автомат.

98.Обобщения КА: асинхронные автоматы.

99.Обобщения КА: автоматы над термами.

194

Список литературы

1.Автоматное управление асинхронными процессами в ЭВМ и дискретных системах/ под ред. В. И. Варшавского. М.: Наука,

1986.

2.Динамические системы. Режим доступа:

http://ru.wikipedia.org/wiki/%D0%94%D0%B8%D0%BD%D0%B0%

D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0% D1%8F_%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BC% D0%B0

3.Котов В. Е. Сети Петри / В. Е. Котов. М.: Наука, 1984. 158с.

4.Кудрявцев В. Б. Введение в теорию автоматов / М.: Наука, 1985.

320 с.

5.Питерсон Дж. Теория сетей Петри и моделирование систем / Пер. М. В. Горбатовой [и др.]; под ред. В. А. Горбатова. М.: Мир, 1984. 264 с.

Упражнения позаимствованы из следующих источников:

1. Дворяшина Т. П. Методические указания для проведения практических занятий по теме «Модели динамического поведения» курса «Теория вычислительных процессов и структур» / Т. П. Дворяшина, А. П. Мартынов; Уфимский государственный авиационный технический университет. Уфа: УГАТУ, 1998.

2.Дворяшина Т. П. Задачи и упражнения по теме «Сети Петри»: Методические указания к практическим занятиям по курсу «Теория вычислительных процессов и структур». Уфа: УГАТУ,

1998.

195

Предметный указатель

А
Автомат Тьюринга .......................			178
Активность перехода	сети	Петри
уровня 0.............................................			62
Активность перехода	сети	Петри
уровня 1.............................................			62
Активность перехода	сети	Петри
уровня 2.............................................			62
Активность перехода	сети	Петри
уровня 3.............................................			62
Активность перехода	сети	Петри
уровня 4.............................................			63
Алгоритм построения	усеченного
дерева достижимости сети Петри
...........................................................			84
Асинхронность...................................			8
Асинхронные автоматы...............			180
Асинхронный процесс ......................			10
Асинхронный процесс	автономный
...........................................................			10
Асинхронный процесс простой			......20
Асинхронный процесс	управляемый
...........................................................			19
Асинхронный процесс эффективный
...........................................................			17
В
Вероятностный автомат............			180
Г
Грамматика ...................................			166
Грамматика регулярная ...............			168
Граф сети Петри ............................			43
Д
Дерево достижимости сети Петри
...........................................................			82
Диаграмма переходов......................			28

Диаграмма					переходов
полумодулярная			...............................			28
Динамическая система.....................						7
Динамическая					система
детерминированная ..........................						8
Допустимая			последовательность
классов			эквивалентности
асинхронного процесса				...................		15
Достижимая			маркировка			сети
Петри ...............................................						51
			З
Задача достижимости сети Петри
...........................................................						77
Задача	минимизации				конечного
автомата.......................................						161
Задача покрываемости сети Петри
...........................................................						77
Задача сохранения сети Петри						.... 96
			И
Инициатор		асинхронного			процесса
...........................................................						10
			К
Класс	рекурсивно			перечислимых
языков .............................................						166
Классы			эквивалентности
асинхронного процесса				...................		15
Комплект .........................................						35
Конечный автомат.......................						148
Конечный автомат Мура ...........						149
Конечный		автомат		абстрактный
.........................................................						148
Конечный автомат автономный 175
Конечный автомат без памяти..						176
Конечный		автомат		без потери
информации ...................................						176
Конечный автомат инициальный148

196

Конечный автомат Мили.............			149
Конечный	автомат		над термами
.........................................................			183
Конечный автомат связный ........			176
Конечный автомат сильно связный
.........................................................			176
Конечный	автомат		структурный
.........................................................			148
Конечный автомат-часы .............			175
		М
Максимальная		последовательность
запусков	переходов		маркированной
сети Петри ......................................			62
Максимальная		последовательность
классов		эквивалентности
асинхронного процесса....................			15
Максимальная			траектория
асинхронного процесса....................			11
Маркированный граф			120
Маркировка сети Петри ................			40
Маркировка		сети	t-
тупиковая .........................................			60
Маркировка сети Петри тупиковая
...........................................................			60
Минимальный автомат................			161
Множество достижимости			сети
Петри................................................			51
		Н
Непосредственно			достижимая
маркировка сети Петри .................			51
		О
Однородный автомат ..................			179
Отношение		M	асинхронного
процесса............................................			13
Отношение		эквивалентности
асинхронного процесса....................			15
Отображение Париха ....................			37
Отрезок траектории асинхронного
процесса............................................			11

	П
Параллелизм.......................................				7
Переход асинхронного процесса ....				14
Переход сети Петри живой ..........				61
Переход сети Петри пассивный ...				60
Переход сети Петри потенциально
живой ...............................................				60
Переход сети Петри потенциально
мертвый ...........................................				60
Переход сети Петри устойчивый 64
Подпроцесс	асинхронного процесса
...........................................................				24
Позиция сети Петри k-ограниченная
...........................................................				57
Позиция сети Петри безопасная ..				55
Помечающая функция сети Петри
всюду определенная.........................				67
Помечающая функция сети Петри
свободная .........................................				67
Помечающая функция сети Петри
частично определенная		..................		67
Последовательность запусков сети
Петри повторяющаяся		................		104
Последовательность запусков сети
Петри		стационарно
повторяющаяся.............................				105
Преобразование сети Петри LB-
эквивалентное ...............................				107
Преобразование Хэка		для	сети
Петри .............................................				109
Префиксный язык помеченной сети
Петри ...............................................				66
Принцип	монотонности		сетей
Петри ...............................................				51
Пространство комплектов ...........				37
Протокол	простого	асинхронного
процесса ...........................................				20
	Р
Разрешенный переход сети Петри45
Расширенная входная функция сети
Петри ...............................................				42

197

Расширенная	выходная	функция
сети Петри ......................................			42
Расширенная	функция следующего
состояния сети Петри ...................			50
Редукция асинхронного процесса			...25
Редукция диаграммы переходов.....			29
Редукция сети Петри .....................			79
Результант асинхронного		процесса
...........................................................			10
Репозиция асинхронного процесса .21
	С
Сети Петри без петель................			108
Сети Петри бесконфликтные.....			114
Сети Петри раскрашенные		.........	128
Сети Петри с приоритетами .....			125
Сети		Петри
самомодифицирующиеся ..............			129
Сети Петри синхронные ..............			126
Сети Петри	со сдерживающими
дугами .............................................			123
Сеть Петри .....................................			39
Сеть Петри k-ограниченная ..........			57
Сеть Петри автоматная ............			117
Сеть Петри безопасная .................			55
Сеть Петри двойственная.............			42
Сеть Петри живая .........................			61
Сеть Петри инверсная ...................			42
Сеть Петри маркированная ..........			41
Сеть Петри ординарная ..............			109
Сеть Петри персистентная........			114
Сеть Петри помеченная ................			66
Сеть Петри со свободным выбором
.........................................................			119
Сеть Петри сохраняющая .............			58
Сеть Петри строго сохраняющая 58

Сеть Петри устойчивая ................	64
Составная матрица изменений сети
Петри .............................................	100
Состояние сети Петри..................	49
Стандартная форма помеченных
сетей Петри ....................................	70
Счетчиковый автомат ................	179
Т
Траектория асинхронного	процесса
...........................................................	11

У

Уровень активности сети Петри 63

Ф
Фундаментальное уравнение		сетей
Петри .............................................		101
Функция следующего	состояния
сети Петри......................................		49
Э
Эквивалентные автоматы ..........		161
Эквивалентные	состояния
конечного автомата ....................		161
Я
Язык конечного автомата...........		167
Язык контекстно-зависимый ......		166
Язык контекстно-свободный ......		167
Язык регулярный ...........................		167
Язык сети Петри	свободный
терминальный .................................		67
Язык сети Петри терминальный . 67

198