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

Маркировкой μ сети Петри называется функция μ: P→N₀.

Состояние сети Петри определяется её маркировкой. Изменение состояния, вызванное запуском перехода, определяется функцией изменения δ, которую назовём функцией следующего состояния. Эта функция применяется к конкретной маркировке μ и заданному переходу t_j. В результате запуска перехода t_j получается новая маркировка.

Запуск перехода и изменение маркировки называется выполнением сети. При многократном выполнении сети Петри получаются две последовательности: последовательность маркировок (μ⁰, μ¹, μ²,…) и последовательность переходов (), которые при этом были запущены. Эти две последовательности связаны соотношением μ^k+1=δ(μ^k, ).

Для сети Петри C=(P,T,I,O) с маркировкой μ маркировка μ^’ называется непосредственно достижимой из μ, если существует такой переход t_j, что

δ(μ, )= μ^’.

Маркировка μ” называется достижимой из маркировки μ, если существует последовательность маркировок (μ, μ₁, μ₂,…, μ_k, μ”) такая, что каждая следующая маркировка в этой последовательности непосредственно достижима из предыдущей.

Множество достижимости R(C, μ) представляет собой набор всех маркировок сети Петри С, достижимых из маркировки μ.