Маркировка и срабатывание сети Петри

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

На рисунке а) изображена начальная маркировка в виде вектора . Здесь разрешенными являются переходы . При срабатывании перехода образуется новая маркировка + .

Правило новой маркировки: во всех входных функциях перехода из каждой позиции удаляется по одной фишке, которая ведет в данный переход и прибавляется по одной фишке для каждой дуги, ведущей из данного перехода в другую позицию (выходную позицию данного перехода). Т.о. если срабатывает переход , для заданной сети Петри, то фишка удаляется из p₁ и переходит в p₂, которая является выходной позицией t₁, но т.к. выходной позицией является также и p₁, то начальная маркировка при срабатывании примет вид:

При срабатывании фишки удаляются из всех входных позиций разрешенного перехода и помещаются во все выходные позиции данного перехода. Т.о. функция следующего состояния будет (1,1,0,0).

Если при первой маркировке срабатывает :

При второй маркировке единственным разрешенным переходом является :

. В этой позиции ни один из переходов не разрешен. Срабатывание сети Петри заканчивается. Такое положение называется тупиком. Срабатывание сети Петри из начальной маркировки может быть изображено в виде дерева:

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

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

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

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