1. Для предлагаемой в таблице (см. приложение) по варианту, со-ответствующему номеру в журнале, сети Петри, заданной в виде дву-дольного ориентированного мультиграфа, выполните следующее:
1) определите сеть Петри в виде C = (P, T, I, O);
2) определите расширенные входную и выходную функцию;
3) определите мультиграф в виде G = (V, A);
4) нарисуйте граф инверсной сети Петри и опишите ее как C = (P,
T, I, O);
5) нарисуйте граф двойственной сети Петри и опишите ее как C =
= (P, T, I, O);
6) выполните сеть Петри, записав последовательность переходов s = t j 1, …, t jk и последовательность маркировокm0, …,m k.
2. Постройте граф сети Петри для следующей структуры сети Петри:
P ={ p 1,
p 2},
T ={ t 1,
t 2, t 3},
I (t 1)=
{ р 1},
O (t 1)=
{ p 1, p 2},
I (t 2)=
{ p 1},
O (t 2)=
{ p 2},
I (t 3)=
{ p 2}.
O (t 3)={}.
ПРИМЕР РЕШЕНИЯ И ОФОРМЛЕНИЯ
ДОМАШНЕГО ЗАДАНИЯ 1
Двудольный ориентированный мультиграф (по варианту из прило-жения):
Решение
1. Определите сеть Петри в виде C = (P, T, I, O).
P ={ p 1, p 2,, pn } – это конечное множество позиций. T =
= { t 1, t 2,, tm } – это конечное множество переходов. I является вход-
ной функцией, O – выходная функция. Обе функции являются отоб-ражениями из переходов в комплекты позиций.
В нашем случае эта четверка будет выглядеть следующим образом:
P ={ p 1, p 2, p 3, p 4}, T ={ t 1, t 2, t 3, t 4, t 5, t 6},
I (t 1)={ p 1}, O (t 1)={ p 2},
I (t 2)={ p 1}, O (t 2)={ p 2, p 3},
I (t 3)={ p 1}, O (t 3)={ p 3, p 3},
I (t 4)={ p 2}, O (t 4)={ p 3},
I (t 5)={ p 3, p 3}, O (t 5)={ p 4},
I (t 6)={ p 4}. O (t 6)={ p 1}.
2. Определите расширенные входную и выходную функции.
Для нашей сети Петри расширенные входная и выходная функции будут:
I (p 1)={ t 6}, O (p 1)={ t 1, t 2, t 3},
I (p 2)={ t 1, t 2}, O (p 2)={ t 4},
I (p 3)={ t 2, t 3, t 3, t 4}, O (p 3)={ t 5, t 5},
I (p 4)={ t 5}. O (p 4)={ t 6}.
3. Определите мультиграф в виде G = (V, A).
Граф сети Петри есть двудольный ориентированный мультиграф
G = (V, A), где V = { v 1, v 2,, vs } – множество вершин, которое, в свою очередь, можно разделить на два непересекающихся подмножества позиций и переходов; а A = { a 1, a 2,, ar } – комплект направленных
дуг, ai = (v j, vk), где v j, vk Î V, т. е. в нашем случае эти множества будут такими:
V = { p 1, p 2, p 3, p 4, t 1, t 2, t 3, t 4, t 5, t 6};
A ={(p 1, t 1), (p 1, t 2), (p 1, t 3), (t 1, p 2), (t 2, p 2), (t 2, p 3), (t 3, p 3),
(t 3, p 3), (p 2, t 4), (t 4, p 3), (p 3, t 5), (p 3, t 5), (t 5, p 4), (p 4, t 6), (t 6, p 1)}.
4. Нарисуйте граф инверсной сети Петри и опишите ее как C =
= (P, T, I, O).
Инверсная сеть Петри определяется из исходной C = (P, T, I, O) перестановкой входной и выходной функций – C = (P, T, O, I). т. е. граф для инверсной нашей сети Петри будет выглядеть так:
Множества переходов и позиций будут те же, что и в исходной се-ти, а входная и выходная функции соответственно примут вид:
I (t 1)={ p 2}, O (t 1)={ p 1},
I (t 2)={ p 2, p 3}, O (t 2)={ p 1},
I (t 3)={ p 3, p 3}, O (t 3)={ p 1},
I (t 4)={ p 3}, O (t 4)={ p 2},
I (t 5)={ p 4}, O (t 5)={ p 3, p 3},
I (t 6)={ p 1}. O (t 6)={ p 1}.
5. Нарисуйте граф двойственной сети Петри и опишите ее C =(P, T, I, O).
Двойственной к сети Петри C = (P, T, I, O) является сеть Петри
C =(T, P, I, O),которая получается в результате перестановки пози-ций и переходов. В нашем случае граф двойственной сети Петри вы-глядит следующим образом:
Множество переходов, множество позиций, входная и выходная функции:
P ={ p 1, p 2, p 3, p 4, p 5, p 6}, T ={ t 1, t 2, t 3, t 4},
I (t 1)={ p 6}, O (t 1)={ p 1, p 2, p 3},
I (t 2)={ p 1, p 2}, O (t 2)={ p 4},
I (t 3)={ p 2, p 3, p 3, p 4}, O (t 3)={ p 5, p 5},
I (t 4)={ p 5}. O (t 4)={ p 6}.
6. Выполните сеть Петри, записав последовательность переходов
s = t j 1,, t jk и последовательность маркировокm0,,m k.
Выполнением сети Петри управляет количество и распределение фишек в сети. Фишки находятся в кружках и управляют выполнением переходов в сети. Сеть Петри выполняется посредством запусков пе-реходов. Переход запускается удалением фишек из его входных пози-ций и образованием новых фишек, помещаемых в его выходные пози-ции.
Определим следующую последовательность переходов:
s = t 20, t 41, t 52, t 63, t 34, t 55, t 66, t 17, t 48.
Ниже приведена последовательность маркировок.
Запуски могут осуществляться до тех пор, пока существует хотя бы один разрешенный переход. Когда не остается ни одного разрешенного перехода, выполнение прекращается.
μ1 = (0, 1, 1, 0) μ2 = (0, 0, 2, 0)
μ3 = (0, 0, 0, 1) μ4 = (1, 0, 0, 0)
μ5 = (0, 0, 2, 0) μ6 = (0, 0, 0, 1)
μ7 = (1, 0, 0, 0) μ8 = (0, 1, 0, 0)
μ9 = (0, 0, 1, 0)
Мы видим, что именно такая ситуация сложилась на последней маркировке. Для запуска перехода t 5 необходимо во входной позиции p 3иметь две фишки,а у нас только одна.
КОНТРОЛЬНЫЕ ВОПРОСЫ
1. Где используются сети Петри?
2. Почему граф СП – двудольный?
3. Почему граф СП – орграф?
4. Почему граф СП – мультиграф?
5. Как расшифровать теоретико-формальное представление СП С =
= (P, T, I, O)?
6. Чем расширенная входная функция отличается от обычной?
7. Почему в графе СП вершин множество, а дуг – комплект?
8. Какой переход называется разрешенным?
9. Как можно выполнить сети Петри?
10. Что такое множество достижимости для сети Петри?
11. Какая маркировка называется непосредственно достижимой из исходной?
12. Какие фишки называются разрешающими?
