Построение дерева достижимости

На рисунке показан пример маркированной сети Петри (СП).

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

1. Корнем дерева является начальная маркировка сети . Для начальной маркировки определяются разрешенные переходы и новые маркировки, появляющиеся при срабатывании переходов;

2. Маркировкам, непосредственно достижимым из , ставятся в соответствие вершины ДД следующего уровня. Дуги от начальной маркировки к непосредственно достижимым из нее маркировкам помечаются переходом, срабатывание которого переводит в новую маркировку, называемую маркировкой первого уровня;

3. Определяют маркировки, непосредственно достижимые из всех маркировок первого уровня. Для вновь полученных маркировок второго уровня определяют разрешенные переходы и т.д.

Процесс построения ДД завершается, когда всем вершинам очередного уровня ветвления соответствуют дублирующие, внутренние или тупиковые маркировки:

- маркировку, ранее уже встречавшуюся на ДД, называют дублирующей;

- маркировки (вершины ДД), ветвление из которых лишь увеличивает количество маркеров в позициях сети, называют внутренними;

- маркировка называется тупиковой, если для нее нет разрешенных переходов.

Задание. Для СП, показанной на рисунке, построить семь этапов ДД и сделать заключение о полученном результате.

Рекомендуемая литература

Информационные технологии на железнодорожном транспорте: Учеб. Для вузов ж.-д. трансп. /Э.К. Лецкий, В.И. Панкратов, В.В. Яковлев и др.; Под ред. Э.К. Лецкого, Э.С. Поддавашкина, В.В. Яковлева. – М.: УМК МПС России, 2000. – 680с.

Не нашли, что искали? Воспользуйтесь поиском: