Маркирование Mj достижимо из Mj (Mi|-Mj), если оно непосредственно достижимо из некоторого маркирования непосредственно достижимого из Mj.

Условимся обозначать через R(M0) объединение множества всех маркирований, достижимых из R(M0)={M0}U{Mi|M0|-Mi}

Наглядным представлением множества R(M0) и всех возможных последовательностей маркирований в произвольной сети Петри является граф Gм(в орбщем случае бесконечный ) достижимых из М0 маркирований. Вершинам графа Gм сопоставляются элементы R(M0). Дуга помеченная символом соответствующего перехода t, проводится из вершины Mi в вершину Мj тогда, когда Mi|-Mj (Mj достижимо по переходу t из Mi).

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

Сеть Петри, удовлетворяющую только условию 1, называют безопасной, а условиям 2 и 3 – живой.

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

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

Одним из известных методов такого конструирования является метод подстановки вместо элемента сети подсистем специального вида, так называемых хорошо сформированных блоков. Используя идеи структурированного программирования, мы будем использовать для подстановки двухполюсные блоки (один вход – один выход).

Сеть N называется двухполюсным блоком, если в ее двухполюсном графе содержится две и только две вершины .

такие, что и , где и — соответственно множество входных и выходных вершин относительно .

Иными словами в вершину , называемую входным полюсом блока, не заходит ни одной дуги, а из вершины , называемой выходным полюсом блока, не исходит ни одной дуги.

По виду периферийных элементов – полюсов — будем различать ТТ, РР, РТ, ТР блоки, характеризуемые тем, что пара вершин соответствует следующим комбинациям:

Переход – переход (ТТ);

Позиция – позиция (РР);

Позиция – переход (РТ);

Переход – позиция (ТР).

Замыканием блока будем называть сеть Петри, формируемую путем связывания выходной и входной вершин блока. При этом для ТТ-блока вводится дополнительная позиция, а для РР-блока – дополнительный переход.

Блок называется хорошо сформированным, если его замыкание представляет собой правильную, то есть живую и безопасную сеть Петри.

Сети, построенные с использованием хорошо сформированных блоков, являются хорошо сформированными.

Рассмотрим два вида блоков, для которых условия хорошей сформированности являются простыми, благодаря наложению определенных условий на их топологию. Это автоматные и маркируемые блоки (А-блоки и М-блоки).

Автоматным блоком называется блок, в котором для любого его перехода t, не являющегося входным или выходным полюсом, имеет место .

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

Условия хорошей сформированности для А-блоков и М-блоков симметричны относительно названия вершин. Дадим это определение:

А-блок (М-блок) является хорошо сформированным блоком, то есть его замыкание – правильная сеть Петри, если

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

Под С-блоком будем понимать блок, в котором нет ограничений, свойственных как А-блоку, так и М-блоку.

Это боки общего вида, требующие анализа на корректность. Они предназначены для отображения некоторых стандартных часто встречающихся особенностей функционирования дискретных объектов. Поэтому анализ такого блока проводится только один раз, и этот блок включается в библиотеку правильных стандартных блоков, а в дальнейшем используется без доказательства его корректности.

Еще один прием конструирования правильных сетей – вставка позиций.

Вставка позиции определена для любой правильно упорядоченной пары переходов t_i, t_j некоторого правильного блока.

Пару переходов t_i, t_j будем называть правильно упорядоченной, если в каждой последовательности сработавших переходов, рассматриваемого блока, а в L- множество таких последовательностей, содержаться оба эти перехода и притом по одному разу, а переход t_i, предшествует переходу t_j. т.о. определенная вставка не нарушает правильности сети.

На базе сетей петри можно строить иерархические модели, используя подход «сверху вниз». При этом старшая модель состоит из вершин-дублеров (соотв. рр-, тт-, рт- и тр- дублеры), которые раскрываются на долее низком уровне иерархии с помощью рассмотренных блоков. Они, в свою очередь, могут содержать вершины-дублеры. Т.о. мы получаем некоторое дерево вложенности.