Разделы

Авто
Бизнес
Болезни
Дом
Защита
Здоровье
Интернет
Компьютеры
Медицина
Науки
Обучение
Общество
Питание
Политика
Производство
Промышленность
Спорт
Техника
Экономика

Определение сети Петри

Прежде чем формально определить понятие сети Петри, введем некоторые обозначении и определения.

 

Будем считать, что арифметические операции распространенны на векторы как покомпонентные операции. Например, K+L = (k1+l1, k2+l2, …, kr+lr), где K = (k1, k2, …, kr) и L = (l1, l2, …, lr). Для векторов также определим следующие операции отношения:

r K=L, если ki=li для всех i;

r KL, если kili для всех i;

r K<L, если KL и существует такое i, что ki<li.

Сетью будем называть тройку (P, T, F), где:

r P – непустое множество элементов сети, называемых местами;

r T – непустое множество элементов сети, называемых переходами;

r F Í P ´ T È T ´ P – отношение инцидентности, сопоставляющее каждому элементу сети xÎX = PÈT множество всех его входных элементов .x = {yÈX: yFx} имножество его выходных элементов x.={yÎX: xFy}, длякоторых выполнены следующие три условия:

· множества мест и переходов не пересекаются, т. е. PT=Æ;

· любой элемент сети инцидентен хотя бы одному элементу другого типа, т. е. для любого xÎPÈT существует такой yÎPÈT, что xFy или yFx;

· сеть не содержит пары мест, у которых совпадают множества входных и выходных переходов, т. е. .p1.p2 или p1.p2.для любых p1, p2ÎP.

 

Сеть конечна, если конечно множество ее элементов X = PÈT.

 

Графическим представлением сети служит двудольный ориентированный граф (в общем случае бесконечный) с двумя типами вершин; вершины-места изображаются кружочками, вершины-переходы – барьерами (а также прямоугольниками или квадратами, если переходы являются неэлементарными объектами). Из вершины x в вершину y ведет дуга, если и только если xFy.

 

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

 

Разметка (или маркировка) сети – это функция M: P→N, которая сопоставляет каждому месту pÎP некоторое неотрицательное целое число M(p)– разметку места p. В графическом представлении сети разметка места p изображается помещением в вершину-кружок числа М(р) или, если это число невелико, соответствующего числа точек (фишек).

 

Сеть Петри – это набор N = (P, T, F, W, M0), где:

r (P, T, F) – конечная сеть;

r M0начальная разметка сети;

r Wфункция кратности дуг. Функция W сопоставляет каждой дуге uÎF положительное целое число uw = W(u) – так называемую кратность дуги u.

 

В графическом представлении сети N кратность uw>1 дуги u отмечается либо числом nw, которое вписывается рядом с изображением дуги u, либо пучком из nw кратных дуг, соединяющих соответствующие элементы сети. Кратность дуги, равная 1, при изображении сети Петри никак не отмечается. Сеть Петри N, в которой W(y) = 1 для всех дуг yÎF, называется ординарной.

 

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

 

Если предположить, что все места сети N строго упорядочены каким-либо образом, т. е.

P = (p1, …, pn), то разметку M сети (в том числе начальную разметку) можно задать как вектор чисел M = (m1, …, mn) такой, что mi = M(pi) для любого i, 1 ≤ i ≤ n.

 

Если = {pi1, …, pik} – подмножество мест из P, то условимся через М() обозначать множество разметок мест {М(pi1) , …, M(pik)}. Если представить как вектор

= (pi1, …, pik), то М() обозначает вектор (М(pi1) , …, M(pik)), называемый проекцией разметки М на . На основе отношения инцидентности F и функции кратности дуг W можно ввести функцию инцидентности F : P ´ T È T ´ P N такую, что F(x, y) = 0, если Ø(xFy), F(x, y) = W(x, y) в остальных случаях. Если места сети упорядочены, то можно каждому переходу t сопоставить два целочисленных вектора .F(t)= (a1, …, an) и

F.(t)= (b1, …, bn), длиной n=|P|, для которых ai = F(pi, t) и bi = F(t, pi) для всех i.

 

Переход t может сработать при некоторой разметке M сети N, если каждое входное место р перехода t имеет разметку не меньшую, чем кратность дуги, соединяющей p и t, т. е. М(р) ³ F(p, t) для всех рÎ .t. Это условие можно переписать в векторной форме следующим образом: M ³ .F(t). Для ординарной сети Петри условие срабатывания перехода означает, что любое входное место этого перехода содержит хотя бы одну фишку, т. е. имеет ненулевую разметку.

 

Срабатывание перехода t при разметке M порождает разметку M¢ = M - .F(t) + F. (t), т.е. M¢(р) = M(р) - F(p, t) + F(t, p) для всех рÎ Р. Таким образом, срабатывание перехода t изменяет разметку так, что разметка каждого его входного места р уменьшается на кратность дуги, соединяющей p и t, а разметка каждого его выходного места увеличивается на кратность дуги, соединяющей t и p.

 

На множестве разметок можно ввести отношение [ > непосредственного следования разметок: М [ > M¢ тогда и только тогда, когда существует такой переход t Î T, что

M ³ .F(t) и M¢ = M - .F(t) + F. (t).

 

Будем использовать уточняющее обозначение М [t > M¢, если M¢ непосредственно следует после M в результате срабатывания перехода t.

 

Говорят, что разметка M¢ достижима от разметки M, если существует последовательность разметок M, M1, M2, …, M¢ и слово t = t1 t2tk в алфавите T такие, что

М [t1 > M1[t2 > M2 …[tk > M¢.

 

Слово t в этом случае называется последовательностью срабатываний, ведущих от М к М¢. Обобщим отношения непосредственного следования до отношения ¢¢M¢ достижима от M¢¢, используя обозначение М [> M¢ или М [t > M¢, если уточняется последовательность срабатываний. При этом последовательность t может быть пустой, т. е. M достижима от M.

 

Множество {M¢: М [> M¢} разметок, достижимых в сети N от разметки М, обозначим через R(N, M). Множество R(N) = R(N, M0), т. е. множество всех разметок, достижимых в N от начальной разметки M0, называют множеством достижимых разметок сети N. (Заметим, что М Î R(N, M) и M0 Î R(N).)

 

Множеством последовательностей срабатываний сети N или свободным языком сети N называется множество L(N) всех последовательностей срабатываний, ведущих от M0 к каждой достижимой в N разметке, т. е.

L(N) = {t Î T*: существует такая разметка M Î R(N), что M0 [t > M}.

 

 

Рис. 1 Пример сети Петри

 

На рис. 1 изображена сеть Петри N, в которой P = (p1, p2, p3) и T = (t1, t2, t3, t4). Функция инцидентности F сети N задается с помощью табл. 1 и 2, в которых на пересечении строки х и столбца у стоит число F(x, y):

Таблица 1 Функция инцидентности переходов с местами     Таблица 2 Функция инцидентности мест с переходами
F(ti, pj) p1 p2 p3 F(ti, pj) t1 t2 t3 t4
t1 p1
t2 p2
t3 p3
t4  

 

Начальная разметка M0 задается следующим образом: M0(p1) = 1, M0(p2) = 2, M0(p3) = 0 или в векторной форме M0 = (1, 2, 0).

 

При разметке M0 могут сработать переходы t1 и t2, т. к. M0 = (1, 2, 0) ³ .F(t1) = (1, 0, 0),

M0 ³ .F(t2) = (1, 2, 0). Переходы t3 и t4 не могут сработать.

 

В результате срабатывания перехода t1 разметка M0 сменяется на разметку (1,3,0), а в результате срабатывания перехода t2 разметка M0 сменяется на разметку (0,0,1). Обе новые разметки непосредственно следуют после M0 в рассматриваемой сети.

 

Разметка M Î R(N) называется тупиковой, если в сети N не существует ни одного перехода, который может сработать при этой разметке.

 

Граф разметок сети N – это ориентированный граф, множество вершин которого образовано множеством R(N) достижимых в N разметок, а дуги графа представляют возможные изменения разметок сети N: из вершины М в вершину М¢ ведет дуга, помеченная символом перехода t тогда и только тогда, когда М [t > M¢.

 

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

 

Рис. 2 Начальный фрагмент графа разметок сети Петри

 

На рис. 2 показан начальный фрагмент графа разметок сети на рис. 1. Этот граф бесконечен, т. к. бесконечно множество R(N) достижимых разметок для рассматриваемой сети N. Язык сети N тоже является бесконечным и включает пустое слово e, а также слова t1, t2, t1t1, t1t2, t2t3, t2t4, t1t1t1, t1t1t2, t1t2t3, t1t2t4, t2t4t1, t1t1t1t1, t1t1t1t2, t1t1t2t3, t1t1t2t4, t1t2t4t1, …. Для рассматриваемой сети N тупиковыми являются разметки (0,2,0), (0,3,0), …, (0,n,0), ….

 

Следующее свойство характеризует эффект увеличения начальной разметки в сети Петри.

 

А. Для любых сетей Петри N = (P, T, F, W, M0) и N ¢= (P, T, F, W, M0 + K), где K произвольный целочисленный вектор с неотрицательными элементами, справедливы следующие свойства:

r L(N) Í L(N¢);

r M Î R(N) Þ (M + K) Î R(N¢);

r М1 [t > M2 Þ (M1 + K) [t > (M2 + K).

 

Дата публикации:2014-01-23

Просмотров:721

Вернуться в оглавление:

Комментария пока нет...


Имя* (по-русски):
Почта* (e-mail):Не публикуется
Ответить (до 1000 символов):







 

2012-2018 lekcion.ru. За поставленную ссылку спасибо.