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

Информация - Компьютеры, программирование

Другие материалы по предмету Компьютеры, программирование

Скачать Бесплатно!
Для того чтобы скачать эту работу.
1. Пожалуйста введите слова с картинки:

2. И нажмите на эту кнопку.
закрыть



i 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, μ).

На основе введённых понятий можно сформулировать ряд свойств сети Петри, характеризующих её в процессе смены маркировок назовём их поведенческими свойствами сети Петри. Определим наиболее важные из них.

  1. Достижимость данной маркировки. Пусть имеется некоторая маркировка μ, отличная от начальной. Тогда возникает вопрос достижимости: можно ли путём запуска определённой поледовательности переходов перейти из начальной в заданную маркировку.
  2. Ограниченность. Сеть Петри называется k- ограниченной, если при любой маркировке количество фишек в любой из позиций не превышает k. В частности, сеть называется безопасной, если k равно 1. Кроме того, сеть называется однородной, если в ней отсутствуют петли и одинарной (простой), если в ней нет кратных дуг.
  3. Активность. Сеть Петри называется активной, если независимо от дотигнутой из μ0 маркировки существует последовательность запусков, п

s