|
99 Если эту процедуру повторять снова и снова, каждая достижимая маркировка окажется порождённой. Однако получившееся дерево достижимости может оказаться бесконечным. Будет порождена каждая маркировка из множества достижимости, поэтому для любой сети Петри с бесконечным множеством достижимости соответствующее дерево также должно быть бесконечным. Даже сеть Петри с конечным множеством достижимости может иметь бесконечное дерево (рис. 4.6). (1.0) (0.1) I0,0) I"(0.1) I'г 0.0) Рисунок 4.6 Простая сеть Петри с бесконечным деревом достижимости Дерево представляет все возможные последовательности запусков переходов. Всякий путь в дереве, начинающийся в корне, соответствует допустимой последовательности переходов. Для превращения дерева в полезный инструмент анализа необходимо найти средства ограничения его до конечного размера. Заметим, что если какое-то представление бесконечного множества конечно, то бесконечное множество маркировок должно отобра |
187 Заметим, что маркировка (0,0,1) пассивная; никакой переход в ней не является разрешённым, поэтому никакие новые маркировки из этой пассивной маркировки в дереве порождаться не будут. Кроме того, необходимо отметить, что маркировка (0,0,1), порождаемая запуском t3 в (0,2,1), была уже порождена непосредственно из начальной маркировки запуском t2. Если эту процедуру повторять снова и снова, каждая достижимая маркировка окажется порождённой. Однако, получившееся дерево достижимости может оказаться бесконечным. Будет порождена каждая маркировка из множества достижимости, поэтому для любой сети Петри с бесконечным множеством достижимости соответствующее дерево также должно быть бесконечным. Даже сеть Петри с конечным множеством достижимости может иметь бесконечное дерево (рисунок 5.17) (1.0) (O.I) (1,0) (О, I) I” (I.O) 1Рис. 5.17. Простая сеть Петри с бесконечным деревом достижимости 188 Дерево представляет все возможные последовательности запусков переходов. Всякий путь в дереве, начинающийся в корне, соответствует допустимой последовательности переходов. Для превращения дерева в полезный инструмент анализа необходимо найти средства ограничения его до конечного размера. Заметим, что если какое-то представление бесконечного множества конечно, то бесконечное множество маркировок должно отображаться в такое представление. В общем случае это приведёт к потери информации и, возможно, к тому, что некоторые свойства сетей Петри определить будет нельзя, но всё зависит от того, как представление будет получено. Приведение к конечному представлению осуществляется несколькими способами. Нам необходимо найти те средства, которые ограничивают введение новых маркировок (называемых граничными вершинами) на каждом шаге. Здесь могут помочь пассивные маркировки маркировки, в которых нет разрешённых переходов. Эти пассивные маркировки называются терминальными вершинами. Другой класс маркировок это маркировки, ранее встречавшиеся в дереве. Такие дублирующиеся маркировки называются дублирующими вершинами; никакие последующие маркировки рассматривать нет нужды все они будут порождены из места первого появления дублирующей маркировки в дереве. Таким образом, в дереве маркировка (0,1,1), получившаяся в результате выполнения последовательности //, /2, /$, не будет порождать какие-либо новые вершины в дереве, поскольку она ранее встречалась в дереве в результате выполнения последовательности /2 из начальной маркировки. Для сведения дерева достижимости к конечному представлению используется ещё одно средство. Рассмотрим последова |