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

Состояние сети Петри определяется ее маркировкой. Пространство состояний сети Петри, обладающей п позициями, есть множество всех маркировок, т.е. Е". Изменение в состоянии, вызванное запуском перехода, определяется функцией перехода S или функцией следующего состояния. Когда эта функция применяется к маркировке М и переходу t.

(если он разрешен), то в соответствии с (2.7) получается новая маркировка М' = b\M,tj). Она, как уже говорилось, получается

изъятием, фишек из позиции p_t таких, что ff Ф 0 (ц.₍. > ff)_} и

помещением фишек впозиции р_к такие, что f-_k^0. Процесс создания новых маркировок продолжается до тех пор, пока в сети Петри при данной маркировке существует хоть один разрешенный переход. Если же при некоторой маркировке М(о) ни один переход не разрешен, то такая маркировка называется тупиковой.

При выполнении сети Петри получается две последовательности:

1) последовательность маркировок

{М(О),М(1),М(2),...};

3) последовательность запущенных переходов

{t_j0,t_j1,t_j2,…}.

Эти две последовательности связаны следующим соотношением:

М(θ + 1) = δ(M(θ),t_jτ). (2.8)

Если в результате запуска перехода при маркировке М образуется новая маркировка М', то говорят, что М' достижима из М.

Множество достижимости R(PN,M)сети ПетриPNcмаркировкой М есть множество всех М_к, достижимьгх из М.

Маркировка М принадлежит R(PN,M), если существует какая-либо последовательность изменяющих М на М.

Множество достижимости R(PN, М) для сети РN = {&,Р,7',F,M₀} с маркировками М есть наименьшее множество маркировок, определенных следующим образом:

а) М' ε R(PN,M);

б) если М' εR(PN,M) и М" = δ(M’,t_j) для некоторого t_j ε T, то M" ε R(PN,M).

Вернемся к примеру на рисунке 2.1. При начальной маркировке М_о - [2,2,0] могут сработать переходы t₁ (в результате получаем М₁’ = [2,3,0]) и t₇ (получается маркировка M₁” = [1,0,1]). Каждая из полученных маркировок порождает новые, в результате чего получается дерево маркировок, фрагмент которого показан на рисунке 2.2. Обратим внимание на то, что в дереве маркировок могут встречаться повторяющиеся маркировки. В этом случае дальнейшее построение дерева ведется только для одной из них.

Если выделить путь по дугам графа маркировок, начинающийся в вершине М_о и заканчивающийся в различных вершинах М', и выписать подряд все встречающиеся символы переходов, то полученное слово образует последовательность срабатываний сети, а их совокупность - свободный язык сети Петри- L(PN,M₀).

Так, язык рассматриваемой сети включает слова:

{λ, t₁, t₂, t₁t₁, t₁t₂, t₂t₁, t₂t₃, t₂t₄, t₁t₁t₁, t₁t₁t₂, t₁t₂t₁, t₁t₂t₃, t₁t₂t₄, t₂t₁t₁, t₂t₃t₁, t₂t₄t₁, t₁t₁t₁t₁, t₁t₁t₁t₂, t₁t₁t₂t₁, t₁t₁t₂t₃, t₁t₁t₂t₄, t₁t₂t₁t₁, …}

Здесь λ – пустой символ, соответствующий начальной маркировке М₀.