10. Структура сетей Петри. Способы задания сетей Петри. Графы сетей Петри.

Элементы дискретных систем – события и условия. Ситуация в асинхронной системе формируется с помощью операций, называемых условиями реализации событий. Условия имеют емкость. Емкость = 0, если условие не выполнено, и равна n, если выполнено с i-кратным запасом. Условие соответствует таким явлениям дискретной системы, как наличие данных для выполнения оператора программ, состояние регистра и тому подобные. Определённое сочетание условий позволяет реализоваться некоторому событию. А реализация события имеет некоторые условия: Кружок без фишек – условие. Кружок с одной фишкой – активное условие. С двумя фишками – с двукратным выполнением условий. Линия – событие (переход).

Структура сетей Петри Сеть Петри является четверкой C=(P,T,I,O) P=(p1,p2,..,pn) – множество ситуаций или позиций. |P|=n. T=(t1,t2,..,tm) – множество переходов. |T|=m. I: - это входная функция для перехода I=I(tj), j=от 1 до m O: - выходная функция. O=O(tj), j=от 1 до m Кратность входной позиции pi для перехода в pj – это число #(pi,I(tj)), а также #(pi,O(tj)) Если аргументом входной и выходной функций являются не переходы, а позиции, то также функции называют расширенными функциями входа и выхода.

Граф G сети Петри – есть двудольный ориентированный мультиграф. G=(V,A) где V – множество вершин V = (V1,V2,..Vk) A=(a1,a2,..as) ai=(Vj,Vk) Множество V может быть разбито на два непересекающихся множества. Для любой дуги ai=(Vj,Vk)

Сети Петри: определение, структура, способы задания.

 

Определение 1:

    Обычной сетью Петри называется конечный двудольный ориентированный граф <V, E>, где V = P T, P T = — разбиение множества вершин, E (PT) (TP) – отношение инцидентности вершин.

 

Определение 2:

Сеть Петри N является четверкой N = (P, Т, I, O), где

 P={p₁, p₂, ..., p_n} — конечное множество позиций, n0;

 T={t₁, t₂,...,t_m} — конечное множество переходов, m0;

 I: T P — входная функция, сопоставляющая переходу мультимножество его входных позиций;

 О: T P — выходная функция, сопоставляющая переходу мультимножество его выходных позиций.

Позиция pP называется входом для перехода tT, если pI(t). Позиция pP называется выходом для перехода tT, если pO(t). Структура сети Петри определяется ее позициями, переходами, входной и выходной функциями.

 

Способы представления сети Петри:

1) Перечисление элементов множеств позиций, переходов, перечисление элементов комплектов входной и выходной функций. Пример:

N =(P, T, I, O),

P={p₁, p₂, p₃},

T={t₁, t₂},

I(t₁)={ p₁, p₁, p₂}, O(t₁)={p₃},

I(t₂)={ p₁, p₂, p₂}, O(t₁₂)={p₃}.

 

2) Наиболее наглядным представлением сети Петри является е¨ графическое представление, которое представляет собой двудольный, ориентированный мультиграф.

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