Синтез комбинацонных схем и конечных автоматов, сети Петри
множество переходов (конечное),
I: T → P (3.2.4)
функция входов (отображение множества переходов во входные позиции),
O: T → P (3.2.5)
функция выходов (отображение множества переходов в выходные позиции).
Если
pi
I (tj)
, то pi
– входная позиция
j - го перехода,
если pi
I
(tj)
, то pi
– выходная
позиция
j - го перехода.
Для наглядного представления сетей Петри используются графы.
Граф сети Петри есть двудольный ориентированный мультиграф
G = (V,
),
(3.2.6)
где V = P U T , причём P ∩ T = Ш.
Исходя из графического представления сети Петри, её можно определить и так:
C = (P, T, A), (3.2.7)
где А – матрица инцидентности графа сети.
Определим понятие маркированной сети Петри – оно является ключевым для любой сети.
Маркировка μ сети Петри C = (P, T, I, O) есть функция:
N = μ(P), N
N,
(3.2.8)
отображающая множество позиций на множество натуральных чисел. Маркировку можно также определить как вектор:
μ = {μ1, μ2,…, μn} , (3.2.9)
где n
= │P │, а μi
N. Между
этими определениями
есть связь:
μi = μ (pi) (3.2.10)
На графе маркировка отображается ссответствующим числом точек в каждой позиции. Точки называются маркерами или фишками. Если фишек много (больше трёх), то их количество отображается числом.
Таким образом, маркированная сеть Петри представляет собой пятёрку элементов:
M = (P, T, I, O, μ). (3.2.11)
Пример простейшей сети Петри:
p1
▪▪▪
t1 p3
p2 ▪
Рисунок 3.2.1 – Пример сети Петри
Правила работы с сетями Петри.
Сеть Петри выполняется посредством запуска переходов. Переход может быть запущен в том случае, когда он разрешён. Переход является разрешённым, если каждая из его входных позиций содержит число фишек не меньшее, чем число дуг из неё в данный переход.
Процедура запуска состоит в удалении из каждой входной позиции перехода числа фишек, равного числу дуг из неё, и в выставлении в каждой выходной позиции числа фишек, равного числу дуг, входящему в неё.
Проиллюстрируем сказанное на примере уже нарисованной сети Петри. Запустим в ней переход t1 – он является разрешённым:
p1
▪
t1 p3
▪
p2 ▪
Рисунок 3.2.2 – Пример запуска перехода сети Петри
Пространство состояний и поведенческие свойства сетей Петри.
Пусть имеется маркированная сеть Петри:
M = (P, T, I, O, μ) (3.2.12)
У неё n позиций. В каждой позиции не более N фишек. Тогда пространство сотояний есть множество всех возможных маркировок сети. Определим δ – функцию следующего состояния.
Если переход tj разрешён при текущей маркировке μ , то следующая маркировка μ’ определится так:
μ’ = δ (μ, tj) (3.2.13)
Если переход tj не разрешён, то δ не определена.
Пусть {tj0, tj1,…, tjs} – последовательность запущенных переходов. Тогда ей будет соответствовать последовательность {μ0, μ1,…,μs+1}, то есть
μk+1 = δ(μk, tjk) (3.2.14)
На основании
последнего
равенства можно
определить
понятие непосредственно
достижимой
маркировки.
Для сети C
= (P, T, I ,O) маркировка
μ’
называется
непосредственно
достижимой
из μ , если существует
такой переход
tj
T, при
котором
μ' = δ(μ , tj) (3.2.15)
Можно распространить это понятие на множество достижимых из данной маркировок. Определим множество достижимых из μ маркировок R(C, μ) следующим образом:
во - первых,
μ
R(C, μ);
во - вторых,
если μ’
R(C, μ), μ’
= δ(μ , tj)
и μ’’
= δ(μ’, tk),
то и μ’’
R(C, μ).
На основе введённых понятий можно сформулировать ряд свойств сети Петри, характеризующих её в процессе смены маркировок – назовём их поведенческими свойствами сети Петри. Определим наиболее важные из них.
Достижимость данной маркировки. Пусть имеется некоторая маркировка μ, отличная от начальной. Тогда возникает вопрос достижимости: можно ли путём запуска определённой поледовательности переходов перейти из начальной в заданную маркировку.
Ограниченность. Сеть Петри называется k- ограниченной, если при любой маркировке количество фишек в любой из позиций не превышает k. В частности, сеть называется безопасной, если k равно 1. Кроме того, сеть называется однородной, если в ней отсутствуют петли и одинарной (простой), если в ней нет кратных дуг.
Активность. Сеть Петри называется активной, если независимо от дотигнутой из μ0 маркировки существует последовательность запусков, приводящая к запуску этого перехода.
Реально
вводят понятия
нескольких
уровней активности
для конкретных
переходов.
Переход tj
T называется:
а) пассивным (L0- активным), если он никогда не может быть запущен;
б) L1- активным, если он может быть запущен последовательностью переходов из μ0 хотя бы один раз;
в) L2- активным, если для любого числа K существует последовательность запусков переходов из μ0 , при которой данный переход может сработать K и более раз;
г) L3- активным, если он является L2- активным при K → ∞.
Обратимость. Сеть Петри обратима, если для любой маркировки μ
R(C, μ0)
маркировка
μ0 достижима
из μ.Покрываемость. Маркировка μ покрываема, если существует другая маркировка μ’
R(C, μ0)
такая, что в
каждой позиции
μ’ фишек
не меньше, чем
в позициях
маркировки
μ.Устойчивость. Сеть Петри называется устойчивой, если для любых двух разрешённых переходов срабатывание одного из них не приводит к запрещению срабатывания другого.
Существуют два основных метода анализа сетей Петри: матричные и основанные на построении дерева покрываемости.
Первая
группа методов
основана на
матричном
представлении
маркировок
и последовательностей
запуска переходов.
Для этого определим
две матрицы
размерности
количество
позиций
количество
переходов,
связанные со
структурой
сети. Первая
матрица называется
матрицей входов: