Реферат: Синтез комбинацонных схем и конечных автоматов, сети Петри

Пример простейшей сети Петри:

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, μ);