Сети Петри

Сети Петри представляют собой модель описания потоков событий и являются модельной интерпретацией асинхронного процесса. Понятие “событие” в данном случае может быть интерпретировано как изменение значения какой-либо компоненты ситуации асинхронного процесса. Связь между событиями выражается с помощью некоторого числа условий, каждое из которых имеет 2 значения: условие выполнено или условие не выполнено.

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

Сеть Петри задаётся множеством позиций Р, множеством переходов Т, функциями I и O и маркировкой μ.

Ø, I: T→P^*, O: T→P^*, маркировка μ представляет собой вектор с количеством компонент, совпадающим с числом позиций Р. Каждая компонента может принимать значения из множества натуральных чисел либо 0.

Множество P^* представляет собой . Функции I и О могут быть определены не на всём множестве Т.

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

Обычно вершины множества Р изображают кружками, а вершины множества Т – планками. При определении функционирования сетей Петри вводится понятие фишек, которые отличаются точками позиций. Маркировка μ определяет расположение фишек по позиции.

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

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

 

 

Пример:

μ={3;1;0;1}

P:{p₁,p₂,p₃,p₄}

T:{t₁,t₂}

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

I(t₂)= {p₄}

O(t₁)= {p₃,p₄ }

O(t₂)= { p₂,p₂ }