Шаг 6.
Сети Петри.
Пространство состояний сети Петри

    На этом шаге мы введем пространство состояний сети Петри.

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

    Пусть дана сеть Петри C = (P, T, I, O) с начальной маркировкой m0. Эта сеть может быть выполнена последовательными запусками переходов. Запуск разрешенного перехода tj в начальной маркировке образует новую маркировку m1 = b( m0, tj). В этой новой маркировке можно запустить любой другой разрешенный переход, например, tk, образующий новую маркировку m2 = b(m1, tk). Этот процесс будет продолжаться до тех пор, пока в маркировке будет существовать хотя бы один разрешенный переход. Если же получена маркировка, в которой ни один переход не разрешен, то никакой переход не может быть запущен, функция следующего состояния не определена для всех переходов, и выполнение сети должно быть закончено.

    При выполнении сети Петри получаются две последовательности: последовательность маркировок ( m0, m1, m2, …) и последовательность переходов, которые были запущены (tj0, tj1, tj2, ...). Эти две последовательности связаны следующим соотношением: b(mk, tjk) = mk+1 для k = 0, 1, 2, ... . Имея последовательность переходов и m0, легко получить последовательность маркировок сети Петри, а имея последовательность маркировок, легко получить последовательность переходов, за исключением нескольких вырожденных случаев. Обе эти последовательности представляют описание выполнения сети Петри.

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

Определение.
Для сети Петри C = (P, T, I, O) с маркировкой m маркировка m' называется непосредственно достижимой из m, если существует переход tj, принадлежащий T, такой, что b (m, tj) = m'.

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

Определение.
Множество достижимости R(C, m) для сети Петри C = (P, T, I, O) с маркировкой m есть наименьшее множество маркировок, определенных следующим образом:
  1. m принадлежит R(C, m) ;
  2. Если m' принадлежит R(C, m) и m'' принадлежит b(m', tj) для некоторого tj, принадлежащего T, то, m'' принадлежит R(C, m) .

    Для сети Петри, изображенной на рисунке 1, и маркировки m = (1, 0, 0) непосредственно достижимыми являются две маркировки: (0, 1, 0) и (1, 0, 1). Из (0, 1, 0) нельзя достичь ни одной маркировки, так как ни один переход не разрешен. Из (1, 0, 1) можно получить (0, 1, 1) и (1, 0, 2).


Рис.1. Маркированная сеть Петри

    Со следующего шага мы начнем рассматривать использование сетей Петри для моделирования.




Предыдущий шаг Содержание Следующий шаг