Состояние сети Петри определяется ее маркировкой. Запуск пере-хода изменяет состояние сети Петри посредством изменения марки-ровки сети. Пространство состояний сети Петри, обладающей n пози-
циями, есть множество всех маркировок, т. е. N n. Изменение в состо-янии, вызванное запуском перехода, определяется функцией измене-ния δ, которую мы назовем функцией следующего состояния. Когда эта функция применяется к маркировке μ (состоянию) и переходу t j, она образует новую маркировку (состояние), которая получается при за-пуске перехода t j в маркировке μ. Так как t j может быть запущен
только в том случае, когда он разрешен, то функция δ(μ, t j) не опреде-лена, если t j не разрешен в маркировке μ. Если же t j разрешен, то d (m, t j) = m¢, где m¢ есть маркировка, полученная в результате удале-ния фишек из входов t j и добавления фишек в выходы t j.
Определение 1.8. Функция следующего состояния δ: Nn ´ Т ® Nn для сети Петри С = (Р, Т, I, О) с маркировкой μ и переходом t j Î Т
определена тогда и только тогда, когда m (pi) ³ #(pi, I (t j)) для всех
pi Î P. Еслиd(m, t j)определена,тоd(m, t j)=m¢,где дляm¢(pi) == m(pi) – #(pi, I (t j)) + #(pi, O (t j)) для всех pi Î P.
Пусть дана сеть Петри С = (Р, Т, I, О) с начальной маркировкой m0. Эта сеть может быть выполнена последовательными запусками пере-ходов. Запуск разрешенного перехода t j в начальной маркировке об-
разует новую маркировку m1 = d (m0, t j). В этой новой маркировке можно запустить любой другой разрешенный переход, например tk, образующий новую маркировку m 2 = d(m1, t k). Этот процесс будет продолжаться до тех пор, пока в маркировке будет существовать хотя бы один разрешенный переход. Если же получена маркировка, в кото-рой ни один переход не разрешен, то никакой переход не может быть запущен, функция следующего состояния не определена для всех пе-реходов, и выполнение сети должно быть закончено.
При выполнении сети Петри получаются две последовательности:
последовательность маркировок (m0,m1,m2,...)и последовательность
переходов,которые были запущены(t j 0, t j 1, t j 2,...).Эти две последова-тельности связаны соотношением d (m k, t jk) = m k +1 для k = 0, 1, 2,...
Имея последовательность переходов и m0, легко получить последова-тельность маркировок сети Петри, а имея последовательность марки-ровок, легко получить последовательность переходов, за исключением нескольких вырожденных случаев. Таким образом, обе эти последова-тельности представляют описание выполнения сети Петри.
Пусть некоторый переход в маркировке μ разрешен и, следователь-но, может быть запущен. Результат запуска перехода в маркировке μ есть новая маркировка m¢. Говорят, что m¢ является непосредственно достижимой из маркировкиμ,иными словами,состояниеμ'непосред-ственно получается из состояния μ.
Определение 1.9. Для сети Петри С = (Р, Т, I, О)с маркировкойμмаркировка m¢ называется непосредственно достижимой из μ, если
существует переход t j Î Т, такой, что d (m, t j) = m¢.
Можно распространить это понятие на определение множества до-стижимых маркировок данной маркированной сети Петри. Если μ' непосредственно достижима из μ, a m¢¢ – из m¢, говорят, что m¢¢ до-стижима изμ.Определим множество достижимости R (С, μ)сетиПетри С с маркировкой μ как множество всех маркировок, достижи-мых из μ. Маркировка m¢ принадлежит R (C, μ), если существует какая-
либо последовательность запусков переходов, изменяющих μ на m¢.
Определение 1.10. Множество достижимости R (C, μ)для сетиПетри С = (Р, Т, I, О)) с маркировкой μ есть наименьшее множество маркировок, определенных следующим образом:
1) μÎ R (C, μ);
2) если m¢ Î R (C, μ) и m ¢¢ = d (m¢, t j) для некоторого t j Î Т, то
m¢¢Î R (C, μ).
Для сети Петри, показанной на рис. 1.17, и маркировки μ = (1, 0, 0) непосредственно достижимыми являются две маркировки: (0, 1, 0) и (1, 0, 1). Из (0, 1, 0) нельзя достичь ни одной маркировки, так как
ни один переход не разрешен. Из (1, 0, 1) можно получить (0, 1, 1) и (1, 0, 2). Далее мы покажем, что множество достижимости R (C, μ) име-
ет вид {(1, 0, n), (0, 1, n) | n ≥ 0}.
Рис. 1. 17. Маркированная сеть Петри
Удобно распространить функцию следующего состояния на отоб-ражение маркировки и последовательности переходов в новую марки-ровку. Для последовательности переходов (t j 1, t j 2, ¼, t jk) и маркиров-
ки μ маркировка m ¢ = d (m, t j 1, t j 2, ¼, t jk) есть результат запусков: сна-чала – t j 1, затем – t j 2 и так далее до t jk. (Такая операция, конечно, возможна только в том случае, если каждый переход к моменту его запуска разрешен.)
Определение 1.11. Расширенная функция следующего состоянияопределяется для маркировки μ и последовательности переходов
σ Î Т * (где Т * –множество всех подмножеств множества(булеан)пе-
реходов) следующими соотношениями: d (m, t j, s) = d (d (m, t j), σ), δ(μ, λ) = μ. Обычно мы применяем эту расширенную функцию.