Формализация функционирования сетей Петри заключается в последовательной смене ее маркировок.
Пусть задана сеть Петри , где , , с начальной маркировкой , где — число позиций, тогда функционирование сети Петри представляется как последовательность смены маркировок .
Сеть Петри останавливается, если эта последовательность конечна и не останавливается в противном случае.
Определение. Маркировка называется ТУПИКОВОЙ, если является последней маркировкой в конечной последовательности срабатывания.
Функционирование сети Петри опишем рекурсивными уравнениями.
есть некая функция от маркировки, зависящей от маркировки на предыдущем шаге функционирования и — возбужденные переходы на к-ом шаге, то есть
Функция может быть случайной, так как должна выбрать из всех возбужденных переходов только один.
Функция детерминированная, то есть четко определенная.
Рассмотрим первое уравнение и два вектора:
— вектор возбуждения переходов,
— вектор срабатывания переходов.
Заметим, что в таблице инцидентности находятся числа .
Дадим содержательную интерпретацию векторов .
Вектор определяет на сколько уменьшится маркировка сети Петри при срабатывании -ого перехода.
Вектор определяет насколько изменится маркировка сети Петри при срабатывании — ого перехода.
Откуда находим
, где — числитель — ой строки, — знаменатель — ой строки.
, где — вектор разностей .
Рассмотрим уравнение . Оно задает вектор возбуждаемых переходов на — ом шаге функционирования сети Петри
Определение. Для определения функции возбуждения переходов необходимо ввести отношения сравнения векторов – целых чисел длинной . Если заданы две маркировки и , то будем говорить, что маркировка , если для всех (производится покомпонентное сравнение векторов и ).
Дадим содержательную интерпретацию отношения . Если покомпонентно вектор больше вектора , то выполняется соотношение .
Аналогично выводятся соотношения .
Условием возбуждения переходов является
, то есть число меток в каждой позиции должно быть больше или равно кратности дуг ведущих из данной позиции в переход . Для вычисления вектора необходимо сравнить покомпонентно текущую маркировку с числителями строк таблицы инцидентности.
Таким образом осталась не определена функция смены маркировок , которая случайно или по какому-то закону выбирает из возбужденных переходов срабатываемый.
Пример. Пусть задана сеть Петри двудольным графом и таблицей инцидентности.
Вычислим вектора .
Вычислим вектор возбуждения переходов . Рассмотрим начальную маркировку . Проверяем условие возбуждения переходов. Так как условие возбуждения переходов выполняется, то вектор возбуждения переходов будет . Предположим сработал второй переход, тогда получим вектор маркировок
,тогда
и так далее.
Определение. Маркировка ДОСТИЖИМА из маркировки если существует последовательность маркировок сети Петри, оканчивающаяся маркировкой , где
, где — строка в алфавите переходов . То есть при функционировании сети Петри порождается строка в алфавите переходов.
Определение. МНОЖЕСТВО ДОСТИЖИМЫХ МАРКИРОВОК для сети Петри из маркировки есть всевозможные маркировки такие, что из маркировки достижима маркировка при конечном числе срабатываний переходов.
Если маркировка — начальной маркировке сети Петри, то множество достижимых маркировок называется МНОЖЕСТВОМ ДОСТИЖИМЫХ МАРКИРОВОК СЕТИ ПЕТРИ.
Определение. СВОБОДНЫЙ ЯЗЫК СЕТИ ПЕТРИ есть множество конечных последовательностей срабатывания сети Петри
, то есть таких, что из начальной маркировки получается достижимая маркировка сети Петри .
СВОБОДНЫЙ ЯЗАК СЕТИ ПЕТРИ — это множество строк в алфавите ведущих от начальной маркировки сети к каждой допустимой (достижимой) маркировке сети Петри .
Множество свободных языков, порождаемых всевозможными сетями Петри, образуют класс свободных языков .
Определение. ПОМЕЧЕННАЯ СЕТЬ ПЕТРИ есть совокупность трех объектов , где
— сеть Петри,
— помечающий алфавит,
— помечающая функция (отображение), ставящее в соответствие каждому переходу знак алфавита .
Пример. Пометим сеть Петри следующего вида
Зададим алфавит . Помечающую функцию представим в следующем виде
Тогда помеченная сеть Петри будет иметь вид:
Определение. ПРЕФИКСНЫЙ ЯЗЫК ПОМЕЧЕННОЙ СЕТИ ПЕТРИ Есть всевозможные строки в алфавите такие, что
Это есть множество значащих строк, принадлежащих языку в помечающем алфавите , соответствующих одной из возможных последовательностей срабатывания сети Петри , задаваемая помечающей функцией .
Определение. ТЕРМИНАЛЬНЫЙ ЯЗЫК ПОМЕЧЕННОЙ СЕТИ ПЕТРИ .Удобно рассматривать не свободный язык сети Петри , а его подмножество терминальных сток, ведущих от начальной маркировки к некоторой фиксированной маркировки .
То есть терминальный язык есть всевозможные строки в алфавите такие, что помечающая последовательность переводит начальную маркировку сети Петри в заданную маркировку .
Пример. Пусть задана сеть Петри двудольным графом
Введем помечающий алфавит и пометим данную сеть Петри. Эта сеть Петри порождаюет свободный язык сети Петри , строками которого являются следующие последовательности срабатывания переходов
Префиксный язык сети Петри .
Терминальный язык сети Петри .
В общем случае эта сеть Петри порождает следующий терминальный язык .
ТЕОРЕМА 2.5. О мощности классов языков сети Петри.
Введем следующие обозначения.
Пусть — языки, которые могут быть порождены всевозможными сетями Петри.
Пусть — всевозможные префиксные языки, порождаемые всевозможными сетями Петри.
Пусть — терминальные языки, соответствующие всевозможным маркировкам всевозможных сетей Петри.
— счетно. Тогда мощность класса терминальных языков сетей Петри превосходит мощность классов префиксных языков, причем .
ДОКАЗАТЕЛЬСТВО.
Класс префиксных языков порождается всевозможными последова-тельностями срабатывания всевозможных сетей Петри, причем только тех последовательностей, которые заканчиваются тупиковой маркировкой. Понятно, что класс терминальных языков более мощен, чем класс префиксных языков и включает часть его, так как помимо последовательностей срабатывания, приводящих к тупиковым маркировкам, содержит и последовательности срабатываний, приводящих к всевозможным заключительным маркировкам , в том числе и к тупиковым.
Окончание доказательства.
