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

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

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

Определение 2.8. Функция следующего состояния б : Nn X Т -> -> Nn для сети Петри С = (Р, Т, I, О) с маркировкой р и переходом tj£T определена тогда и только тогда, когда р(/?г) > і^іРь /(tj)) для всех pi £ Р. Если 8(р, tj) определена, то 6(р, t}) = ft', где (Pi) = — #(Pi. Htj)) + ШРи 0(h)) для всех pt £ P.

Пусть дана сеть Петри С = (Р, Т, /, О) с начальной маркировкой |і°. Эта сеть может быть выполнена последовательными запусками переходов. Запуск разрешенного перехода t} в начальной маркировке образует новую маркировку р1 = 6(р°, tj). В этой новой маркировке можно запустить любой другой разрешенный переход, например tb, образующий новую маркировку р2 = б([д,1, th). Этот процесс будет продолжаться до тех пор, пока в маркировке будет существовать хотя бы один разрешенный переход. Если же получена маркировка, в которой ни один переход не разрешен, то никакой переход не может быть запущен, функция следующего состояния не определена для всех переходов, и выполнение сети должно быть закончено.

При выполнении сети Петри получаются две последовательности: последовательность маркировок (р°, р1, р2, ...) и последовательность переходов, которые были запущены (tj(h tjlf tj2, ...). Эти две последовательности связаны следующим соотношением: 6(pft, tjk) —

—    pft+1 для k = 0, 1, 2, ... . Имея последовательность переходов и р°, легко получить последовательность маркировок сети Петри, а имея последовательность маркировок, легко получить последовательность переходов, за исключением нескольких вырожденных случаев1). Таким образом, обе эти последовательности представляют описание выполнения сети Петри.

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

Определение 2.9. Для сети Петри С = (Р, Т, /, О) с маркировкой Р маркировка р' называется непосредственно достижимой из р, если существует переход tj € Т, такой, что 6(р, ts) — р'.

Можно распространить это понятие на определение множества Достижимых маркировок данной маркированной сети Петри. Если Р непосредственно достижима из р, а р" — из р', говорят, что р" достижима из р. Определим множество достижимости R(C, р)

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

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

1.   р € R(C, р);

2.   Если р' £ R(C, р) и р" = 6(р', tj) для некоторого t, f Т, то р" еЯ(С, р).

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

Удобно распространить функцию следующего состояния на отображение маркировки и последовательности переходов в новую маркировку. Для последовательности переходов (tjlt tj2, ..., tjk) и маркировки р маркировка р' = 6(р, f/x, tj2, ..., tjk) есть результат запусков: сначала — tjt, затем — tj2 и т. д. до tjk. (Такая операция, конечно, возможна только в том случае, если каждый переход к моменту его запуска разрешен.)

Определение 2.11. Расширенная функция следующего состояния определяется для маркировки р и последовательности переходов с € 7’*2> следующими соотношениями: 6(р, tj, о) = S(6(p, tj), а), в(р. Ц = Р-

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

Упражнения

]. Определите последовательность маркировок для маркированной сети Петри (рис. 2.21) и последовательности переходов /ь і2, із, h, th. Как выглядит соответствующая последовательность переходов для последовательности маркировок (1, 0, 0), (0, 0, 1), (0, 0, 0)?

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

3.   Покажите, что l)R(C, |-і) = Nn.

(д. 6 Nn

4.   Докажите, что если ц' £ R(C, ц), то R(C, n')^R(C, jx).

5.   Докажите,что (x'g/?(С, (j.) тогда и только тогда, когда R(C, [j,') ^ #(С,;х).

6.   Выполняется ли равенство i?(C,u) — u6(u, t*)?

tjZT

7.   Выполняется ли равенство R(C, ц) = U R(C,S([i,ij))?

tj £ T

8.   В некоторых публикациях по сетям Петри множество достижимости маркированной сети Петри называется ее классом маркировок. Более точно класс прямых маркировок сети Петри есть то, что мы определили как множество достижимости. Класс обратных маркировок есть множество достижимости инверсной сети Петри (см. упражнение 9 к разд. 2.2). Тогда класс маркировок маркированной сети Петри есть объединение прямых и обратных классов маркировок. Дайте формальное определение класса прямых маркировок, класса обратных маркировок и класса маркировок сети Петри с маркировкой ц. Затем покажите, что классы маркировок сети Петри разбивают множество всех маркировок на непересекающиеся классы эквивалентности. Для этого требуется показать, что отношение «иметь равные классы маркировок» является рефлексным, симметричным и транзитивным.

9.   Сети Петри со своими фишками и правилами запусков во многом напоминают игры, имеющие игровое поле: шашки, трик-тракО, ним, го и др. Можно

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

а)   Как определено начальное расположение фишек? (Каждый игрок начинает игру, имея одну фишку в «домике»; каждый игрок получ'ает «п» фншек на всем поле по желанию и т. д.)

б)   Какова цель игры? (Захватить фишки своего противника; получить наибольшее количество фишек; как можно скорее избавиться от своих фишек и т. д.)

в)   Не нужно ли раскрасить фишки для разных игроков? (В соответствии с этим определите правила запуска.)

г)   Не стоит лн присвоить очки различным переходам? Тогда очки игрока определятся суммой переходов, запущенных им.

д)   Проанализируйте возникновение таких задач, как повторные запуски переходов, которые образуют новые фишки (выходов больше, чем входов); конечное число фишек, обеспечивающих конец игры.

После того как вы определили свою игру, попытайтесь сыграть в иее с кем- нибудь нз своих друзей. В качестве игрового поля используйте сеть Петри, noKd ^<інную на рис. 2.22.