Общие понятия о сетях Петри

Рис. 3.

Маркировка сети Петри

Следующий пункт - выполнение сети. Для этого надо разобрать исходное понятие - разрешённые переходы. Переход разрешён если каждая из его входных позиций имеет по крайней мере столько фишек, сколько дуг из этой позиции в данный переход. Запуск перехода - перенос фишек через разрешённые переходы из исходных позиций в новые (из исходных позиций фишки удаляются, в новые добавляются). Тогда выполнение сети - процесс запуска переходов. В результате выполнения сети мы получаем новую маркировку µ`.

Например, на рис. 3 разрешены переходы t1, t3, t4, а переход t2 запрещён. Переход t1 разрешён потому, что на входе у него позиция p1 с одной дугой и имеет одну фишку. Переход t2 запрещён, так как входящие в него позиции p2 и p3 не имеют фишек вообще. Переход t3 разрешён, так как в него входит посредством двух дуг позиция p4, имеющая 2 фишки. Переход t4 разрешён, так как имеет на входе он имеет позицию p5 с одной фишкой и одной дугой.

Рис. 4.

Граф сети после запуска в сети рис.3 перехода t4

Рис. 5.

Граф сети после запуска в сети рис.4 перехода t1

Можно заметить, что после последовательного выполнения переходов t4 и t1 переход t2 становится разрешённым.

Функция следующего состояния -

для сети Петри с маркировкой и переходом ti определена тогда и только тогда, когда переход ti разрешён и определяется выражением

где - новая маркировка, получаемая при выполнении перехода ti. Кроме того следует ввести понятие непосредственно достижимой маркировки. Маркировка непосредственно достижима из µ, если существует ti такой, что . Далее следует понятие множества достижимости. Множество достижимости R(C, µ) для сети Петри с маркировкой µ есть наименьшее множестве маркировок, такое, что: а) , б) если и для некоторого tj , то Например, для сети на рис. 6. Множеством достижимости R(C, µ) является множество: [2].