Анализ свойств сети Петри выполняется на основе ее дерева достижимости.

Алгоритм построения дерева достижимости:

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

- если , то ;

- если на пути от корневой вершины к существует вершина , такая что , то ;

- в противном случае значение определяется на основе срабатывания перехода из состояния .

Вершина переопределяется как внутренняя, вершина становится граничной. Алгоритм заканчивает работу, когда все вершины дерева тупиковые, дублирующие или внутренние.

На рисунке 4.9 изображен пример построения дерева достижимости сети Петри.

Рисунок 4.9 – Построение дерева достижимости сети Петри

Проверка свойств сети Петри по дереву достижимости. Сеть Петри является ограниченной тогда и только тогда, когда в её дереве достижимости отсутствует символ . Если сеть Петри ограничена, то по её дереву можно определить емкость каждой позиции как максимальное значение соответствующей компоненты состояния сети. Даже если сеть Петри не ограничена, то емкость можно определить для позиций, в которых отсутствует .

Проверка сети Петри на тупиковые состояния по дереву достижимости не требует пояснений (неконечные состояния не должны быть тупиковыми).

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

Date: 2016-07-25; view: 398; Нарушение авторских прав