Неформальное определение сети Петри.

Читайте также:

(одна из возможных интерпретаций формального объекта)

t₁ p₂ t₃

●

t₂ p₃

●

p₁t₄

T={t₁, t₂, t₃, t₄}

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

p₁ – входное место для перехода t₁

p₂– входное место для перехода t₂

p₃ – входное место для перехода t₃

В данной интерпретации сеть Петри представляет собой размеченный вершиновзвешенный мультиграф со множеством вершин. Из вершины-места, изображаемой кружком, ведет дуга в вершину-переход, изображаемый прямоугольником, тогда и только тогда, когда функция инцидентности F(p_i, t_j)=1. Из вершины-перехода в вершину-место ведет дуга, когда функция инцидентности F(t_k, p_l)=1. Место помечается разметкой. При этом часто эта разметка является числом точек (фишек) внутри кружка (M₀(p_t) # 0).

Динамика поведения моделируемой системы, рассматриваемая в терминах функционирования сети Петри.

Сеть функционирует в дискретные времена, переходя от разметки к разметке. При этом разметка – это функция M: P → {0, 1, 2, 3,… } смены разметок (начиная с М₀), происходящей в результате срабатывания перехода в сети Петри. Переход может сработать при разметке М, если для любого р имеет место неравенство

t_q ∈ T, p_t ∈ P, M(p) – F(p,t) ≥ 0

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

∀ P ∈ P, M'(p) – F(p,t) + F(t,p)

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

Две сети Петри эквивалентны, если они порождают один и тот же язык.

Замечания.

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

2. Как математическая модель сеть Петри занимает место между конечными автоматами и машинами Тьюринга. При этом по выразительной возможности язык сети Петри значительно богаче языка конечных автоматов и приближается к машине Тьюринга.

3. Немаркированная сеть Петри, т.е. сеть, где М=0, есть статичная структура.

4. Последовательность запуска переходов – выполнение сети Петри.

Пример1. Рассмотрим выполнение сети Петри, заданной мультиграфом.

t₂ p₁