ВУЗ:
Составители:
112
ды t
2
, t
5
. Переход называется активным, если он не заблокирован (нетупиковый).
7.3.4. Достижимость и покрываемость
Определение. Задача достижимости. Для данной сети Петри С = (P, T, I, O) с
маркировкой µ и маркировки µ′ определить: µ′ ∈ R(C, µ).
Задача достижимости – основная задача анализа сети Петри. Многие задачи
анализа могут быть сформулированы в терминах такой задачи достижимости.
Множество достижимости сети Петри представляет собой дерево достижимости.
Пусть имеется сеть Петри, представленная на рис. 7.10. Ее начальная маркировка –
(1, 0, 0). В этой начальной маркировке разрешены t
1
и t
2
. Чтобы рассмотреть все мно-
жество достижимости, определим новые вершины в дереве достижимости для других
достижимых маркировок, получающихся в результате запуска каждого из этих двух
переходов. Начальной (корневой) является вершина, соответствующая начальной
маркировке. Дуга, помеченная запускаемым переходом, приводит из начальной мар-
кировки к каждой из новых маркировок (рис. 7.11). Это частичное дерево показывает
все маркировки, непосредственно достижимые из начальной маркировки.
(1, 0, 0)
(1, 1, 0) (0, 1, 1)
t1 t2
t1
t2
t3
P1
P2
P3
Рис. 7.10. Маркированная сеть Петри,
для которой строится дерево достижимости
Рис. 7.11. Первый шаг
построения дерева достижимости
Теперь необходимо рассмотреть все маркировки, достижимые из новых марки-
ровок. Из маркировки (1, 1, 0) можно снова запустить t
1
(получая 1, 2, 0) и t
2
(получая
(0, 2, 1); из (0, 1, 1) можно запустить t
3
(получая 0, 0, 1). Это порождает дерево, изо-
браженное на рис. 7.12. Начиная с трех новых маркировок, необходимо повторить
этот процесс, порождая новые маркировки, которые нужно ввести в дерево, как пока-
зано на рис. 7.13.
(1, 0, 0)
t1 t2
(1, 1, 0)
(0, 1, 1)
(1, 2, 0) (0, 2, 1) (0, 0, 1)
t1 t2 t3
Рис. 7.12. Второй шаг построения дерева достижимости
Страницы
- « первая
- ‹ предыдущая
- …
- 111
- 112
- 113
- 114
- 115
- …
- следующая ›
- последняя »
