TVPS_posobie_13_06_2013

Рис. 42. Исходная сеть Петри (С, )

Шаг 1. Проверяется условие 1 стандартной формы: если сеть содержит переходы без входных или выходных позиций (в нашем случае это переходы t1, t3), то в сеть добавляется еще одна позиция q,

0(q)=1, которая будет входом и выходом каждого перехода сети.

Нетрудно видеть, что такое добавление позиции не меняет условий и результатов запусков каждого из переходов, поэтому новая сеть сохраняет свободный, префиксный и терминальный языки заданной сети (последний с учетом добавления к t компоненты

t(q)=1).

На Рис. 43 показан пример описанного преобразования помеченной сети в сеть, удовлетворяющую первому условию стандартной формы.

Рис. 43. СП, удовлетворяющая условию 1 стандартной формы

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

71

Для каждого перехода t T, который может сработать при начальной разметке 0 (в нашем примере это переходы t1, t3), введем

новый переход t' с пометкой (t')= (t) (то есть t1' , t3' ) (рис. 44).

Каждый из новых переходов имеет в качестве единственной входной позиции включающую позицию on. Выходные дуги для каждого нового перехода заводятся в позиции сети так, чтобы после срабатывания перехода t' разметка позиций сети совпала бы с разметкой исходной сети после срабатывания перехода t при 0, а именно:

I(t')={on},

#(pi, O(t'))= 0(pi) + #(pi, O(t)) #(pi, I(t)).

Пусть некоторая последовательность запусков исходной сети (C, ), ей соответствует последовательность ' сети (С', '). Нетрудно видеть, что существует взаимно-однозначное соответствие между и '. Поэтому предложенное преобразование сохраняет префиксный и

терминальный языки.

Любое слово ( ) L(C, ), L(C) принадлежит также языку новой сети и порождается ее последовательностью ', отличающейся от лишь первым символом перехода (t' в ' вместо t в ). Наоборот, любая последовательность запусков переходов ' новой сети должна начинаться некоторым символом перехода t', так как ни один из «старых» переходов сети не может сработать (все позиции, кроме включающей не имеют фишек). Продолжение последовательности

запусков	переходов ' должно	далее совпадать	с продолжением
некоторой	последовательности	срабатываний	старой сети,
начинающейся символом перехода t.

72

Рис. 44. Сеть Петри, удовлетворяющая условию 2 стандартной формы

Срабатывание перехода t1 меняет разметку 0 на разметку (2, 1, 1), где переход q считается третьей в упорядоченном наборе позиций, а срабатывание перехода t3 меняет разметку 0 на разметку

(0, 0, 1). Поэтому в новой сети (две дуги из t1' в р1, по одной дуге в р2

и q, аналогично для t3' ):

( 0, t1' )=(2, 1, 1) и ( 0, t3' )=(0, 0, 1).

Шаг 3. Чтобы выполнить третье требование стандартной формы СП, для каждого перехода t T такого, что он последним может сработать перед терминальной разметкой t, добавляется новый переход t'' с пометкой (t'')= (t). Входные дуги, ведущие в переход t'', заводятся так, чтобы в точности соответствовать маркировке, предшествующей терминальной, когда запускается t, а выходных дуг переход t'' не имеет (таким образом, при срабатывании этих переходов получим разметку 0 ).

Пусть для нашего примера терминальная маркировка t=(3, 0, 1). Тогда маркировки, предшествующие терминальной:

((2, 0, 1), t1)=(3, 0, 1), ((4, 1, 1), t3)=(3, 0, 1).

73

Таким	образом, нужно ввести переходы t1'' : ( t1'' )= (t1),
t3'' : ( t3'' )=	(t3) (рис. 45).

Для того чтобы при запуске новых переходов получить терминальную маркировку, необходимо при запуске «собрать»

фишки: для t1'' два входа из р1, один вход из q, для t3'' четыре входа из р1, по одному входу из р2 и q.

Рис. 45. СП, удовлетворяющая условию 3 стандартной формы

Следствие. Любой язык из классов L, L , L0, L0 может быть порожден некоторой помеченной сетью в стандартной форме как ее терминальный язык для терминальной разметки t = 0 .

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

74

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

Класс префиксных языков помеченных сетей Петри без -переходов является собственным подмножеством класса

терминальных языков сетей Петри без -переходов:

L L0.

Класс префиксных языков сетей Петри, содержащий префиксные языки всех помеченных сетей, является собственным подмножеством класса терминальных языков сетей Петри, содержащего терминальные языки всех помеченных сетей:

L L0 .

Класс свободных терминальных языков сетей Петри является собственным подмножеством класса терминальных языков помеченных сетей Петри без -переходов:

L0f L0.

Класс свободных префиксных языков для свободных сетей Петри является собственным подмножеством класса префиксных языков помеченных сетей Петри без -переходов:

Lf L.

Класс префиксных языков помеченных сетей Петри без -переходов является собственным подмножеством класса префиксных языков сетей Петри, содержащего префиксные языки

всех помеченных сетей:

L L .

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

языки всех помеченных сетей:

L0 L0 .

75

Построим схему соотношения между классами языков сетей Петри (Рис. 46):

Lf	L		L
Lf	L	0	L	0
0

Рис. 46. Соотношение между классами языков сетей Петри

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

Свойства классов языков сетей Петри

Далее представлен список задач, которые являются типичными для формальных языков:

1)принадлежности (слово L?);

2)пустоты (L= ?);

3)конечности (L конечно?);

4)эквивалентности (языки равны?);

5)включения (L1 L2).

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

				Таблица 5
	Свойства классов языков сетей Петри
Классы языков/	Принадлежности	Пустоты		Эквивалентности
Проблемы		и конечности		и включения
L	Р	Р		Н
L	Р	Р		Н
L0	Р	С		Н
L0	С	С		Н

76

Неразрешимыми проблемами теории языков сетей Петри являются:

изменятся ли префиксные или терминальные языки сети Петри, если из сети удалить некоторый переход;

изменятся ли префиксные или терминальные языки сети Петри, если из некоторой позиции сети удалить фишку.

2.12.Основные задачи анализа сетей Петри

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

Задачи достижимости и покрываемости

Задача достижимости состоит в следующем: для данной маркированной сети Петри (С, 0) и некоторой маркировки ' проверить включение ' R(C, 0).

Многие другие задачи анализа можно сформулировать в терминах задачи достижимости.

А) Проблема тупиков. Определить, принадлежит ли данная тупиковая маркировка множеству достижимости маркированной сети Петри.

Б) Проблема взаимного исключения. Определить, существует

ли маркировка ' R(C, 0), в которой '(pi) 1 и '(pj) 1, где pi и pj – заданные позиции. Иначе говоря, проверить, могут ли в процессе

функционирования сети возникнуть маркировки, в которых в обеих позициях есть фишки.

Задачу покрываемости можно сформулировать следующим образом.

77

Для	данной		сети	Петри С с	начальной		маркировкой	и
некоторой	маркировки			' R(C, )	определить, существует			ли
достижимая из '			маркировка '' такая, что			'' '?
Про	'' говорят, что она покрывает					', а про	' говорят, что она
покрывается		''.
Пример			32. Решить задачу покрываемости начальной
маркировки		0=(100) для сети Петри (Рис. 47).
		p1	t1	p2	t2	p3

t3

Рис. 47. СП для решения задачи покрываемости

Ответ: да, 0 покрывается маркировкой '=(100), которая получена в результате запуска последовательности переходов

=(t1t2t3).

Задачи эквивалентности

Одной из важных задач при использовании сетей Петри является уменьшение размеров сети, в частности, с целью увеличения параллелизма, уменьшения стоимости реализации.

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

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

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

78

между множествами последовательностей запусков переходов сетей имеется взаимно-однозначное соответствие.

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

По сути, все эти задачи связаны с преобразованием исходной сети в новую сеть, которая в определенном смысле эквивалентна

исходной, но возможно, имеет другую структуру.

Определение. Редукцией относительно некоторого набора свойств {z1, z2, …, zk} называется преобразование сети Петри (C, 0) в сеть (C', 0'), таким образом, что

|P T|>|P' T'|,

и все свойства из данного набора сохраняются.

Таким образом, в результате редукции сеть Петри сокращается, что упрощает ее последующий анализ.

Пример 33. Рассмотрим сеть Петри (Рис. 48). Переходы t4 и t5 являются пассивными, позиция p6 также пассивная. Удалим пассивные переходы и позицию.

Алгоритм в общем виде выглядит следующим образом: Шаг 1. Строим список пассивных переходов.

Шаг 2. Для каждого из пассивных переходов удаляем входные и выходные дуги, а затем и сам переход. Если в результате удаления дуг в сети Петри появились изолированные вершины (позиции), то удаляем их.

Шаг 3. Строим список пассивных позиций.

Шаг 4. Для каждой пассивной позиции удаляем входные и выходные дуги, а затем и саму позицию. Если в результате удаления дуг в сети Петри появились изолированные вершины (переходы), то удаляем их.

79

Рис. 48. Исходная сеть Петри с пассивными переходами t4 и t5 и позицией p6

Выполним удаление пассивных переходов и позиций для нашей сети (Рис. 48).

Шаг 1. Строим список пассивных переходов: t4 и t5. Шаг 2. Для каждого перехода:

2.1. Удаляем входные и выходные дуги перехода t4, а затем и сам переход (Рис. 49).

Рис. 49. Сеть Петри после удаления пассивного перехода t4

Так как висячих вершин-позиций в результате удаления данного перехода не появилось, переходим к следующему переходу.

2.2. Удаляем входные и выходные дуги перехода t5, а затем и сам переход (Рис. 50).

80