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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6. Кодирование состояний автомата

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

Если на входы двух элементов памяти подать одновременно один сигнал, то на выходе сигнал возникнет не одновременно. Это явление называется состязаниями элементов памяти.

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

Существует 2 способа кодирования автомата. Первый характеризуется устранением всех состязаний элементов памяти. Для этого всем внутренним

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

Второй способ кодирования связан только с устранением критических состязаний. Методы первой и второй групп имеют свои преимущества и свои недостатки.

Чтобы приступить к кодированию, которое необходимо выполнить для построения в последующем структурной схемы автомата, введем в табл. 6 переходов автомата символ конца цепочки входных символов, например, символ x3, который оказался неиспользуемым в рассматриваемой грамматике. Соответственно, необходимо в таблицу переходов ввести переход из заключительного состояния r11 в начальное состояние r0 по входному символу x3. Новая таблица переходов примет вид, показанный табл. 7, в которой последний столбец отведен для формируемых кодов состояний автомата.

Число внутренних переменных кода, изменяющих свои значения при переходе автомата из одного состояния в другое, есть расстояние по Хеммингу между этими кодами .

Наименьшее число переменных, необходимое для кодирования синхронного автомата с N внутренними состояниями определяется формулой:

n = ] log2 (N) [

] [ - ближайшее сверху к log₂ (N) целое число. Например, при N=13 n

будет равно 4.

Число кодовых переменных, необходимое для кодировки состояния автомата соседними кодами определяется по формуле:

n = 2  ] log2 (N) [ - 1.

Знаком  обозначена операция умножения.

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

В курсовой работе используется код минимальной длины. В связи с этим может возникнуть ситуация, когда все соседние коды заняты, а состояния автомата еще не закодированы в полном объеме. Это требует увеличения расстояния по Хеммингу на следующем шаге кодирования. Кодирование будем осуществлять методом проб и ошибок.

Таблица 7

	x0	x1	x2	x3	x4	x5	x6	x7	Код
r0 нач. сост.					r11	r1	r4	r3	0000
r1	r2				r11				0001
r2	r11				r0				0101
r3		r7			r8		r10		0010
r4					r5		r6		0100
r5					r1				1100
r6			r1						0110
r7			r8						0011
r8						r9			1010
r9		r11							1110
r10								r9	0110
r11 закл. сост.				r0					1000

Таблица 8

	x0	x1	x2	x3	x4	x5	x6	x7	Код
r0 нач. сост.					r11	r1	r4	r3	0000
r1	r2				r11				1000
r2	r11				r0				1001
r3		r7			r8		r10		0100
r4					r5		r6		0010
r5					r1				1010
r6			r1						0011
r7			r8						1100
r8						r9			0110
r9		r11							0111
r10								r9	0101
r11 закл. сост.				r0					0001

Таблица 9

	x0	x1	x2	x3	x4	x5	x6	x7	Код
r0 нач. сост.					r11	r1	r4	r3	0000
r1	r2				r11				0010
r2	r11				r0				0110
r3		r7			r8		r10		0001
r4					r5		r6		1000
r5					r1				1100
r6			r1						1010
r7			r8						1001
r8						r9			0011
r9		r11							0111
r10								r9	0101
r11 закл. сост.				r0					0100

При этом используем направления кодирования состояний, представленные на рис. 4.

r10 r3 r0 r11

r8 r7 r4 r1 r2

r9 r5 r6

Рис. 4

Выполним три варианта кодирования (Таблицы 7, 8, 9), из которых выберем наилучший на основе критерия Махалонобиса. Критерием кодирования автомата считаем минимум функционала Махаланобиса.

,

где M - число переходов. Через (r_i , r_j) обозначено расстояние между кодами r_i и r_j по Хеммингу.

В результате получим, что в первом случае суммарное расстояние по Хеммингу для 20 переходов равно 32, а во втором и третьем случае - 26. Выберем третий вариант.