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

Состояние сети Петри определяется её маркировкой. Запуск перехода изменяет состояние сети Петри посредством изменения маркировки сети. Пространство состояний сети Петри, обладающей n позициями, есть множество всех маркировок, т.е. Nⁿ. Изменение в состоянии, вызванное запуском перехода, определяется функцией изменения d, которую мы назовём функцией следующего состояния. Когда эта функция применяется к маркировке m (состоянию) и переходу t_j, она образует новую маркировку (состояние), которая получается при запуске перехода t_j в маркировке m. Так как t_j может быть запущен только в том случае, когда он разрешён, то функция d (m, t_j) не определена, если t_j не разрешён в маркировке m. Если же t_j разрешён, то , где есть маркировка, полученная в результате удаления фишек из входов t_j и добавления фишек в выходы t_j.

Определение 6. Функция следующего состояния d: Nⁿ´T ® Nⁿ для сети Петри С = (Р, Т, I, O) с маркировкой m и переходом t_jÎT определена тогда и только тогда, когда m (p_i) ³ # (p_i, I (t_j)) для всех p_i Î P. Если d (m, t_j) определена, то , где для всех p_iÎP.

Пусть дана сеть Петри С = (Р, Т, I, O) с начальной маркировкой m. Эта сеть может быть выполнена последовательными запусками переходов. Запуск разрешённого перехода t_j в начальной маркировке образует новую маркировку . В этой новой маркировке можно запустить любой другой разрешённый переход, например t_k, образующий новую маркировку . Этот процесс будет продолжаться до тех пор, пока в маркировке будет существовать хотя бы один разрешённый переход. Если же получена маркировка, в которой ни один переход не разрешён, то никакой переход не может быть запущен, функция следующего состояния не определена для всех переходов, и выполнение сети должно быть закончено.

При выполнении сети Петри получаются две последовательности: последовательность маркировок и последовательность переходов, которые были запущены . Эти две последовательности связаны следующим соотношением: для k = 0,1,2,.... Имея последовательность переходов и m ⁰, легко получить последовательность маркировок сети Петри, а имея последовательность маркировок, легко получить последовательность переходов, за исключением нескольких вырожденных случаев. Таким образом, обе эти последовательности представляют описание выполнения сети Петри.

Пусть некоторый переход в маркировке m разрешён и, следовательно, может быть запущен. Результат запуска перехода в маркировке m есть новая маркировка m'. Говорят, что m' является непосредственно достижимой из маркировки m, иными словами, состояние m' непосредственно получается из состояния m.

Определение 7. Для сети Петри С = (Р, Т, I, O) с маркировкой m маркировка m' называется непосредственно достижимой из m, если существует переход t_jÎT, такой, что d (m, t_j) = m'.

Можно распространить это понятие на определение множества достижимых маркировок данной маркированной сети Петри. Если m' непосредственно достижима из m, а m'' – из m', говорят, что m" достижима из m. Определим множество достижимости R(C, m ) сети Петри С с маркировкой m как множество всех маркировок, достижимых из m. Маркировка m' принадлежит R(C, m ), если существует какая-либо последовательность запусков переходов, изменяющих m на m'. Отношение «достижимости» является рефлексивным, транзитивным замыканием отношения «непосредственной достижимости».

Определение 8. Множество достижимости R (C, m) дли сети Петри С = (Р, Т, I, O)с маркировкой m есть наименьшее множество маркировок, определённых следующим образом:

1. m Î R (C, m);

2. Если m' Î R (C, m) и m'' = d (m', t_j) для некоторого t_j Î T, то m'' Î R (C, m).

Лекция 6

Дата добавления: 2014-12-16