Правила выполнения сетей Петри

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

Переход может запускаться только в том случае, когда он разрешен. Переход называется разрешенным, если каждая из его входных позиций имеет число фишек по крайней мере равное числу дуг из позиции в переход. Кратные фишки необходимы для кратных входных дуг. Фишки во входной позиции, которые разрешают переход, называются его разрешающими фишками. Например, если позиции p₁ и р₂ служат входами для перехода t₄, тогда t₄ разрешен, если p₁ и р₂ имеют хотя бы по одной фишке. Для перехода t₇ с входным комплектом {р₆, р₆, р₆} позиция р₆ должна обладать по крайней мере тремя фишками, для того чтобы t₇ был разрешен.

Определение 1.6. Переход t_j Т, в маркированной сети Петри
С = (Р, Т, I, О) с маркировкой μ разрешен, если для всех p_i P

μ ( p_i ) ≥ #( p_i, I(t_j)) .

Переход запускается удалением всех разрешающих фишек из его входных позиций и последующим помещением в каждую из его выходных позиций по одной фишке для каждой дуги. Кратные фишки создаются для кратных выходных дуг. Переход t₃ с I(t₃) = {р₂} и O(t₃) = {р₇, p₁₃} разрешен всякий раз, когда в p₂ будет хотя бы одна фишка. Переход t₃ запускается удалением одной фишки из позиции р₂ и помещением одной фишки в позицию р₇ и в p₁₃ (его выходы). Дополнительные фишки в позиции р₂ не влияют на запуск t₃ (хотя они могут разрешать дополнительные запуски t₃). Переход t₂; котором I(t₂) = {р₂₁, p₂₃} и O(t₂) = {р₂₃, p₂₅, p₂₅}, запускается удалением одной фишки из р₂₁ и одной фишки из p₂₃, при этом одна фишка помещается в р₂₃ и две – в p₂₅ (так как p₂₅ имеет кратность, равную двум).

Запуск перехода в целом заменяет маркировку μ сети Петри на маркировку μ'. Заметим также, что так как можно запустить только разрешенный переход, то при запуске перехода количество фишек в каждой позиции всегда остается неотрицательным. Запуск перехода никогда не удалит фишку, отсутствующую во входной позиции. Если какая-либо входная позиция перехода не обладает достаточным количеством фишек, то переход не разрешен и не может быть запущен.

Определение 1.7. Переход t_j в маркированной сети Петри с маркировкой μ может быть запущен всякий раз, когда он разрешен. В результате запуска разрешенного перехода t_j образуется новая маркировка μ', определяемая следующим соотношением: μ'( p_i ) = μ( p_i ) – #( p_i, I(t_j)) + #( p_i, O(t_j)).

В качестве примера рассмотрим маркированную сеть Петри, изображенную на рис. 1.8. При такой маркировке разрешены переходы t₁, t₂, t₃. Переходы t₁₄, t₅, t₆ не разрешены, так как ни одна позиций р₂, р₃, р₄, являющихся входами этих переходов, не имеют фишек. Т.е. ни один из переходов t₁₄, t₅, t₆ не может быть запущен. Если запущен переход t₂, то происходит удаление фишки из единственного входа р₁ и помещение двух фишек – по одной в выходы р₂ и р₃. Новая маркировка, полученная в результате запуска показана на рис. 1.15. Далее будем запускать последовательно разрешенные переходы t₄, t₅, t₆, t₃, t₅, t₆, t₁, t₄.Результирующая маркированнаясети Петри представлена на рис. 1.16.

Рис. 1.15. После запуска перехода t₂ Рис. 1.16. Окончательная маркировка

Запуски могут осуществляться до тех пор, пока существует хотя бы один разрешенный переход. Когда не остается ни одного разрешенного перехода, выполнение прекращается.

Мы видим, что именно такая ситуация сложилась на последней маркировке. Для запуска перехода t₄ необходимо во входной позиции p₃ иметь две разрешающие фишки, а у нас только одна.