Сеть петри пример

1. ;

2. ;

3.

В графической форме сеть представлена на Рис.1. Сеть имеет четыре места и три перехода. Отношение задает дуги сети. Так, например, элемент задает четыре дуги: из в и из в с кратностями 2, из в и из в с единичными кратностями. Для перехода справедливо и . Для места можно вычислить и .

Рис. 1: Пример графа сети Петри

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

Пример. Пример маркированной сети.

Рис. 2: Пример маркированной сети Петри

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

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

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

Рис. 3: Новая сеть с маркировкой .

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

1. — имя (идентификатор) t-точки доступа;
2. — некоторый алфавит;
3. — пометочная функция, где . Запись обозначает множество всех конечных и непустых мультимножеств, определённых на множестве .

1. — имя (идентификатор) s-точки доступа;
2. — множество такое, что .

Введённые понятия точек доступа предоставляют возможность ввести две основные операции над сетями Петри для построения композициональных сетей:

1. Операция слияния переходов — позволяет порождать и описывать синхронизацию параллельных процессов (tmerge);

2. Операция слияния мест — позволяет применять к сетям операции последовательной композиции, выбора, итерации и другие (smerge).

Рис. 4: Пример операции слияния переходов

Рис. 5: Пример операции слияния мест

Приведённые операции имеют следующий смысл:

При слиянии мест — определяется набор состояний в сети, которые идентифицируются, как состояние сети, определённое именем s-точки доступа. Слияние различных сетей производится так, что если в одной сети достигнуто описанное состояние, то в другой сети это состояние также получается достигнутым;

При слиянии переходов – определяется алфавит событий, видимых из t-точки доступа. Каждый переход в сети помечается либо невидимым событием, либо комбинацией событий из алфавита точки доступа. Слияние по переходам производится так, что если при срабатывании одной сети возникает некоторая комбинация событий, то эта же комбинация событий происходит во второй сети.

Сеть петри пример

На этом шаге мы рассмотрим перечислим правила выполнения сетей Петри и рассмотрим пример их использования .

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

Переход может запускаться только в том случае, когда он разрешен. Переход называется разрешенным , если каждая из его входных позиций имеет число фишек, по крайней мере, равное числу дуг из позиции в переход. Кратные фишки необходимы для кратных входных дуг. Фишки во входной позиции, которые разрешают переход, называются его разрешающими фишками . Например, если позиции p 1 и p 2 служат входами для перехода t 4 , тогда t 4 разрешен, если p 1 и p 2 имеют хотя бы по одной фишке. Для перехода t 7 c входным комплектом

позиция p 6 должна обладать, по крайней мере, тремя фишками, для того, чтобы t 7 был разрешен. Определение. Переход t j из T в маркированной сети Петри C = (P, T, I, O) с маркировкой m разрешен, если для всех p i , принадлежащих P ,

Переход запускается удалением всех разрешающих фишек из его входных позиций и последующим перемещением в каждую из его выходных позиций по одной фишке для каждой дуги. Кратные фишки создаются для кратных выходных дуг. Переход t 3 с I(t 3 ) =

и O(t 3 ) =

разрешен всякий раз, когда в p 2 будет хотя бы одна фишка. Переход t 3 запускается удалением одной фишки из позиции p 2 и помещением одной фишки в позицию p 7 и в p 13 (его выходы). Дополнительные фишки в позиции p 2 не влияют на запуск t 3 (хотя они могут разрешать дополнительные запуски t 3 ). Переход t 2 , в котором I(t 2 ) = < p 21 , p 23 >и O(t 2 ) =

запускается удалением одной фишки из p 21 и одной фишки из p 23 , при этом одна фишка помещается в p 23 и две — в p 25 (так как p 25 имеет кратность, равную двум).

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

Рассмотрим маркированную сеть Петри с рисунка 1 для иллюстрации правил запуска.

Рис.1. Маркированная сеть Петри. Переходы t 1 , t 3 и t 4 разрешены

При такой маркировке разрешены только переходы t 1 , t 3 и t 4 . Переход t 2 не разрешен, так как ни позиция p 2 , ни позиция p 3 , являющиеся входами перехода t 2 не содержат ни одной фишки. Так как переходы t 1 , t 3 и t 4 разрешены, любой из них может быть запущен. Если запущен переход t 4 , то происходит удаление фишки из каждого входа и помещение фишки в каждый выход. При этом одна фишка удаляется из p 5 , одна фишка помещается в p 3 , а количество фишек в p 4 увеличивается с двух до трех. Новая маркировка, полученная в результате запуска перехода t 4 , показана на рисунке 2.

Рис.2. Маркировка, полученная в результате запуска перехода t 4

В маркированной сети Петри, изображенной на рисунке 2, разрешены переходы t 1 и t 3 . При запуске перехода t 1 осуществляется удаление фишки из p 1 и помещение фишек в p 2 , p 3 и p 4 (в p 4 — две фишки, так как эта позиция является кратным выходом перехода t 1 ). Эта операция образует маркировку, приведенную на рисунке 3.

Рис.3. Маркировка, полученная в результате запуска перехода t 1

В такой маркированной сети Петри переходы t 2 и t 3 разрешены. Запуск перехода t 3 образует новую маркировку (рисунок 4), где две фишки удалены из p 4 , а одна добавлена в p 5 .

Рис.4. Маркировка, полученная в результате запуска перехода t 3

Запуски могут осуществляться до тех пор, пока существует хотя бы один разрешенный переход. Когда не останется ни одного разрешенного перехода, выполнение прекращается.

На следующем шаге мы рассмотрим пространство состояний сети Петри .

Сети Петри. Структура и правила выполнения сетей Петри.

Сети Петри Править

Сети Петри — математический аппарат для моделирования динамических дискретных систем. Впервые описаны Карлом Петри в 1962 году.

Пример работы сети Петри

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

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

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

$ Введите сюда формулу $ ==Структура сетей Петри==

Сеть Петри состоит из 4-х элементов:

• множество позиций P,
• множество переходов T,
• входная функция I,
• выходная функция O.

Пример сети Петри. Белыми кружками обозначены позиции, полосками — переходы, чёрными кружками — метки.

Входная и выходная функции связаны с переходами и позициями. Входная функция I отображает переход t_j в множество позиций I(t_j) , называемых входными позициями перехода . Выходная функция O отображает переход p_i в множество позиций O(p_i) , называемых выходными позициями перехода . Структура сети Петри определяется её позициями, переходами, входной и выходной функциями.

Сеть Петри С является четверкой, C=(P,T,I,O). P=1, p₂, . p_i, p_n> — конечное множество позиций, n>=0. T=< t₁, t₂, . t_j, t_m > — конечное множество переходов, m>=0. Множество позиций и множество переходов не пересекаются, то есть пересечение P и T равно пустому множеству. I: T->P ¥ является входной функцией — отображением из переходов в комплекты позиций. O: P ¥ ->T есть выходная функция — отображение из комплектов позиций в переходы.

Произвольный элемент P обозначается символом p_i , i=1, . n, а произвольный элемент T — символом t_j, j=1, . m.

Правила выполнения сетей Петри Править

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

Переход запускается, если он разрешен. Переход называется разрешенным, если каждая из его входных позиций имеет число фишек по крайней мере равное числу дуг из позиции в переход. Фишки во входной позиции, которые разрешают переход, называются его разрешающими фишками. Например, если позиции р1 и р2 служат входами для перехода t1, тогда t1 разрешен, если р1 и р2 имеют хотя бы по одной фишке. Для перехода t3 с входным комплектом позиция р3 должна иметь не менее 3 фишек для разрешения перехода t3.

Определение. Переход $ t_j in T $ маркированной сети Петри $ C = (P, T, I, O, mu) $ с маркировкой $ mu $ , разрешен, если для всех $ p_j in P $ , $ mu (p_i) geq # (p_i, I(t_j)) $ .

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

>Переход t3 I(t3) = и O(t3) = разрешен каждый раз, когда в р2 будет хотя бы одна фишка. Переход t3 запускается удалением одной фишки из позиции р2 и помещением одной фишки в позицию р3 и р4 (его выходы). Переход t4, в котором I(t4) = и O(t4) = запускается удалением по одной фишке из позиций р4 и р5, при этом одна фишка помещается в р5 и две в р6 (рис. 2).

Определение. Переход $ t_j $ в маркированной сети Петри с маркировкой $ mu $ может быть запущен всякий раз, когда он разрешен. В результате запуска разрешенного перехода $ t_j $ образуется новая маркировка $ mu^ <'>$ :

$ mu^ <'>(p_i) = mu (p_j) — # (p_i, I(t_j) + # (p_i, O(t_j)) $