Лекция: Формальное определение сети Петри

Формально сеть N определяется пятеркой множеств:

,

где или – конечное непустое множество символов, называемых местами (позициями) сети;

или – конечное непустое множество символов, называемых переходами;

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

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

Таблица 3.2 – Функция инциндентности

Таблица 3.3 – Функция инциндентности

– начальная разметка сети Петри, представляющая собой множество мест во множестве целых положительных чисел {0, 1 ,2,…}, которые указывают количество фишек на каждом месте.

Например, для приведенной выше сети:

– множество мест;

– множество переходов;

Начальная разметка:

.

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

,

которая показывает, что к срабатыванию готовы все три перехода. Так как при программной реализации одним процессором два события не могут произойти одновременно, то далее анализ строится на основе случайного выбора.

Пусть, например, сработал переход и образовалась разметка :

.

Переходя от одного вектора разметки к другому, можно записать цепочку срабатывания переходов:

.

Разметки и явились тупиковыми, так как при таких расположениях фишек ни один переход не срабатывает и сеть зависает.

Изложенный способ анализа сети эффективен при небольшом числе переходов. При анализе более сложных сетей целесообразно представлять маркировки в виде «дерева достижимости». Вершиной “дерева” является начальная маркировка сети. “Дерево” представляет собой отрезки линий (рис. 3.10) – векторы разметок.

Рисунок 3.10 – Фрагмент “дерева достижимости” сети Петри

“Дерево достижимости” позволяет выявить тупиковые ситуации и определить условия для достижения конечного множества.