Маркировкой μ сети Петри называется функция μ: P→N0.
Состояние сети Петри определяется её маркировкой. Изменение состояния, вызванное запуском перехода, определяется функцией изменения δ, которую назовём функцией следующего состояния. Эта функция применяется к конкретной маркировке μ и заданному переходу tj. В результате запуска перехода tj получается новая маркировка.
Запуск перехода и изменение маркировки называется выполнением сети. При многократном выполнении сети Петри получаются две последовательности: последовательность маркировок (μ0, μ1, μ2,…) и последовательность переходов (), которые при этом были запущены. Эти две последовательности связаны соотношением μk+1=δ(μk, ).
Для сети Петри C=(P,T,I,O) с маркировкой μ маркировка μ’ называется непосредственно достижимой из μ, если существует такой переход tj, что
δ(μ, )= μ’.
Маркировка μ” называется достижимой из маркировки μ, если существует последовательность маркировок (μ, μ1, μ2,…, μk, μ”) такая, что каждая следующая маркировка в этой последовательности непосредственно достижима из предыдущей.
Множество достижимости R(C, μ) представляет собой набор всех маркировок сети Петри С, достижимых из маркировки μ.