ГЛАВА 2. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ

В этой главе мы дадим формальные определения основных понятий сетей Петри. Основные понятия используются на протяжении всей книги и являются необходимыми для правильного понимания.

Наш формализм основывается на теории комплектов, являющейся обобщением теории множеств. Если вы не знакомы близко с теорией комплектов, предлагаем вам прочитать приложение.

Определения, данныэ здесь, по стилю подобны определениям теории автоматов [130], т. е. определен новый класс машин — автоматная сеть Петри. Как мы увидим позднее (гл. 5—8), такая точка зрейия может привести к некоторым интересным результатам в теории формальных языков и теории автоматов.

2.1. Структура сети Петри

Сеть Петри состоит из четырех элементов: множество позиций множество переходов 7, входная функция I и выходная функция О. Входная и выходная функции связаны с переходами и позициями. Входная функция I отображает переход в множество позиций называемых входными позициями перехода. Выходная функция О отображает переход в множество позиций называемых выходными позициями перехода.

Структура сети Петри определяется ее позициями, переходами, входной и выходной функциями.

Определение 2.1. Сеть Петри С является четверкой, конечное множество позиций, конечное множество переходов, Множество позиций и множество переходов не пересекаются, является входной функцией — отображением из переходов в комплекты позиций. есть выходная функция — отображение из переходов в комплекты позиций.

Мощность множества есть число а мощность множества есть число Произвольный элемент обозначается символом а произвольный элемент символом

Примеры сетей Петри даны на рис. 2.1-2.3.

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

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

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

Определение 2.2. Определим расширенную входную функцию I и выходную функцию

таким образом, что

Для сети Петри на рис. 2.1 расширенными входной и выходной функциями являются:

Рис. 2.1. Структура сети Петри представлена в виде четверки, которая состоит из множества позиций множества переходов входной функции и выходной функции

Рис. 2.2. Структура сети Петри.

Рис. 2.3. Структура сети Петри.

Упражнения.

(см. скан)