5. Работа с сетями Петри

Сеть Петри определяется как формальная система, характеризуемая 4 формальными объектами: S = < P, T, E, M0 >, где

• P - конечное множество позиций;

• T - конечное множество переходов;

• E - конечное множество дуг;

• M0 - начальная маркировка.

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

Процедура минимизации конечного автомата с использованием сети Петри:

1. На сети выделяются 2 позиции, имеющие одинаковое количество одинаковых входных переходов.

2. Позиции склеиваются. При этом множества входящих и исходящих дуг этих позиций объединяются без дублирования.

3. На сети выделяются 2 позиции, имеющие одинаковое

количество одинаковых выходных переходов.

4. Позиции склеиваются. При этом множества входящих и

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

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

4. Если из некоторой позиции по одинаковому переходу xi существует более одной выходной позиции, то такие выходные позиции должны быть склеены.

Процедура повторяется с п. 1 до тех пор, пока позиции сети могут быть склеены.

Рассмотрим построение сети Петри для автоматной грамматики. Выполняя все необходимые правила построения сети и минимизации автомата по сети, последовательно получим сети, приведенные на рис.1 -3. На последней сети Петри проставлены ri, по разметке которых легко сравнить результаты минимизации автомата по сети Петри с минимизацией автомата по методике алгоритма Мура (См. табл. 6).

Рис. 1. Сеть Петри, составленная по автоматной грамматике

Применяя выше названные правила минимизации сети Петри, можно объединить вершины {D, E} и {A,B,C} согласно правилам 3-4. У них имеется на выходе одинаковое количество одинаковых переходов. Затем объединяются вершины {{D,E,}Z} и {S1,S3} согласно правилам 1-2, затем объединяются вершины {S4,{A,B,C}} согласно правилам 1-2. У них имеется на выходе одинаковое количество одинаковых переходов. При этом вершина Z остается в сети и сама по себе, т.к. она имеет входы и от других вершины, отличных от входов объединяемых вершин. Затем объединяем вершины {S6,S8}, имеющие одинаковые входные переходы x7, идущие от одной и той же вершины F. При этом вершину S6 оставляем, поскольку у нее есть вход от еще одной вершины S5. Вершину S8 заменяем на склеенную {S6, S8}, поскольку у нее вход только от вершины F. Построим сеть после преобразования, получим:

Рис. 2. Минимизированная сеть Петри

Если провести параллель между состояниями минимизированного детерминированного автомата и минимальной сетью Петри, то можно установить соответствие:

r0	r1	r2	r3	r4	r5	r6	r7	r8	r9	r10
S	S4,A,B,C	D,E,Z	F	S1,S3	S2	S5	S6	S6,S8	S7	Z