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

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

маркировке Если же разрешен, то где есть маркировка, полученная в результате удаления фишек из входов и добавления фишек в выходы

Определение 2.8. Функция <ледующего состояния для сети Петри с маркировкой и переходом определена тогда и только тогда, когда для всех Если определена, то где для всех

Пусть дана сеть Петри с начальной маркировкой Эта сеть может быть выполнена последовательными запусками переходов. Запуск разрешенного перехода в начальной маркировке образует новую маркировку В этой новой маркировке можно запустить любой другой разрешенный переход, например образующий новую маркировку Этот процесс будет продолжаться до тех пор, пока в маркировке будет существовать хотя бы один разрешенный переход. Если же получена маркировка, в которой ни один переход не разрешен, то никакой переход не может быть запущен, функция следующего состояния не определена для всех переходов, и выполнение сети должно быть закончено.

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

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

Определение 2.9. Для сети Петри с маркировкой маркировка называется непосредственно достижимой из если существует переход такой, что

Можно распространить это понятие на определение множества достижимых маркировок данной маркированной сети Петри. Если непосредственно достижима из а из говорят, достижима из Определим множество достижимости

сети Петри С с маркировкой как множество всех маркировок, достижимых из Маркировка принадлежит если существует какая-либо последовательность запусков переходов, изменяющих на Отношение «достижимости» является рефлексивным, транзитивным замыканием отношения «непосредственной достижимости».

Определение 2.10. Множество достижимости для сети Петри с маркировкой есть наименьшее множество маркировок, определенных следующим образом:

2. Если для некоторого то

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

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

Удобно распространить функцию следующего состояния на отображение маркировки и последовательности переходов в новую маркировку. Для последовательности переходов и маркировки маркировка есть результат запусков: сначала — затем — до (Такая операция, конечно, возможна только в том случае, если каждый переход к моменту его запуска разрешен.)

Определение 2.11. Расширенная функция следующего состояния определяется для маркировки и последовательности переходов следующими соотношениями:

Обычно мы применяем эту расширенную функцию.

Рис. 2.21. (см. скан) Маркированная сеть Петри.

Упражнения

(см. скан)

(см. скан)