Пространство состояний сети Петри

Состояние сети Петри определяется ее маркировкой. Пространство состояний сети Петри, обладающей n позициями, есть множество всех маркировок, т.е. . Изменение в состоянии, вызванное запуском перехода, определяется функцией перехода d или функцией следующего состояния. Когда эта функция применяется к маркировке M и переходу   (если он разрешен), то в соответствии с (2.7) получается новая маркировка . Она, как уже говорилось, получается изъятием фишек из позиции p_i таких, что  и помещением фишек в позиции  такие, что . Процесс создания новых маркировок продолжается до тех пор, пока в сети Петри при данной маркировке существует хоть один разрешенный переход. Если же при некоторой маркировке  ни один переход не разрешен, то такая маркировка называется тупиковой.

При выполнении сети Петри получается две последовательности:

1) последовательность маркировок

;

2) последовательность запущенных переходов

.

Эти две последовательности связаны следующим соотношением

.                                                           (2.8)

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

Множество достижимости  сети Петри P N с маркировкой М есть множество всех , достижимых из М.

Маркировка М ^¢ принадлежит , если существует какая-либо последовательность запусков переходов, изменяющих М на М ^¢.

Множество достижимости  для сети P  c маркировками М есть наименьшее множество маркировок, определенных следующим образом:

a) ;

б) если  и  для некоторого , то .

Вернемся к примеру на рисунке 2.1. При начальной маркировке  могут сработать переходы  (в результате получаем ) и  (получается маркировка ). Каждая из полученных маркировок порождает новые, в результате чего получается дерево маркировок, фрагмент которого показан на рисунке 2.2. Нумеровать маркировки будем по мере получения по глубине и сверху вниз. Обратим внимание на то, что в дереве маркировок могут встречаться повторяющиеся маркировки. В этом случае дальнейшее построение дерева ведется только для одной из них, имеющий меньший номер (остальные одинаковые ветки «обрубаем»).

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

Так, язык рассматриваемой сети включает слова

{ l, t₁, t₂, t₁ t₁, t₁ t₂, t₂ t₁, t₂ t₃, t₂ t₄, t₁ t₁ t₁, t₁ t₁ t₂, t₁ t₂ t₁,

 t₁ t₂ t₃, t₁ t₂ t₄, t₂ t₁ t₁, t₂ t₃ t₁, t₂ t₄ t₁, t₁ t₁ t₁ t₁, t₁ t₁ t₁ t₂, t₁ t₁ t₂ t₁,

 t₁ t₁ t₂ t₃, t₁ t₁ t₂ t₄, t₁ t₂ t₁ t₁,... }

Здесь l - пустой символ, соответствующий начальной маркировке .

= 0	= 1	= 2	= 3	= 4
[2 2 0] M0	t1: [2 3 0] М1
		t1: [2 4 0] M3
			t1: [2 5 0] M6
				t1: [2 6 0] M9
				t2: [1 3 1] M10
			t2: [1 2 1]M7
				t1: [1 3 1] M10 повтор
				t2: [0 0 2] М11
				t3: [2 4 0] М3 повтор
				t4: [2 2 0] М0 повтор
		t2: [1 1 1] M4
			t1: [12 1] Mp7 повтор
			t3: [2 3 0] Mp1повтор
			t4: [2 1 0] M8
				t 1: [2 2 0] М0 повтор
	t2: [1 0 1] М2
		t1: [1 1 1] Mp4 повтор
		t3: [2 2 0] Mp0 повтор
		t4: [2 0 0]M5
			t1: [2 1 0] Mp8 повтор

 

р исунок 2.2 Дерево маркировки сети Петр, показанной на рисунке 2.1