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

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

Определение 3. Маркировка  сети Петри С = (Р, Т, I, O) есть функция, отображающая множество позиций Р в множество неотрицательных целых чисел N:

 P  N

Маркировка  может быть также определена как n-вектор  = (₁, ₂, ..., _n), где п =P и каждое _i  N, i=1,...,n. Вектор  определяет для каждой позиции p_i сети Петри количество фишек в этой позиции. Количество фишек в позиции p_i, есть _i, i=1,...,n. Связь между определениями маркировки как функции и как вектора очевидным образом устанавливается соотношением (p_i)=_i. Обозначение ее в виде функции является несколько более общим и поэтому употребляется гораздо чаще.

Маркированная сеть Петри М = (С, ) есть совокупность структуры сети Петри С = (Р, Т, I, O) и маркировки  и может быть записана в виде М = (Р, Т, I, O, ).

Рис.5.4.

На графе сети Петри фишки изображаются маленькой точкой в кружке, который представляет позицию сети Петри. На рис.5.4 приведен пример графического представления маркированной сети Петри, аналогичной на рис.5.2 с маркировкой (1, 2, 0, 0, 1).

Так как количество фишек, которое может быть определено для каждой позиции, неограниченно, то в целом для сети Петри существует бесконечно много маркировок. Множество всех маркировок сети Петри, обладающей n позициями, есть множество всех n-векторов, Nⁿ. Это множество, хотя и бесконечно, является счетным.

Рис.5.5 Граф сети Петри с очень большой маркировкой.

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

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

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

Определение 4. Переход t_j  T в маркированной сети Петри С = {Р, Т, I, O) с маркировкой  разрешен, если для всех p_i  P

.

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

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

Определение 5. Переход t_j маркированной сети Петри с маркировкой  может быть запущен всякий раз, когда он разрешен. В результате запуска разрешенного перехода t_j образуется новая маркировка , определяемая следующим соотношением: .