Лекция о сетях Петри от Шамаля (Лекция о сетях Петри от Шамаля)

Посмотреть архив целиком

Сети Петри.

Сетью Петри принято называть тройку , где граф сети Петри, – конечное множество позиций (или мест) сети, – конечное множество переходов сети, ; – функции, задающие комплекты входных и, соответственно, выходных позиций переходов сети (здесь – множество всевозможных конечных комплектов элементов множества ); - начальная маркировка (разметка) позиций сети, - множество всевозможных маркировок; функция раскраски, где – множество красок.

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

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

Сети Петри, как правило, рассматриваются с точностью до изоморфизма, то есть имена позиций и переходов являются «связанными» внутри сети и при графическом изображении, вообще говоря, могут не указываться (они необходимы только для ссылок, например, при описании поведения сети):

Определение 1. Сети и , считаются идентичными, если существуют взаимно-однозначные отображения и , такие, что .

Основой определения семантики сетей Петри является функция переходов , в общем случае частичная: Здесь «+» и «-» знаки операций «сложения» и «вычитания» комплектов: , , где . Функция обобщается на множество кортежей переходов ( ): , . Мно-жество маркировок, достижимых из маркировки , обозначается и определяется так: , а множество всех достижимых в сети маркировок (достижимых из начальной маркировки ) так: . Маркировка называется тупиковой, если для всех