Введение в архитектуру компьютеров


Здесь: – переход; O – место - часть 2


Будем использовать следующие обозначения: *t = {p| F (p, t)>0}; t*=

= {p| H (t, p)>0}; *t+ (*t-) – множество таких мест, что существуют дуги из этих мест в переход и эти дуги помечены плюсом (минусом); t+*(t-*) – множество таких мест, что существуют дуги из перехода t в эти места и эти дуги помечены плюсом (минусом). Отметим, что *t+?*t- = Ø для любого t, т. е. если из места в переход существуют кратные дуги, то они должны быть помечены одним и тем же символом. Иначе из-за операции аннигиляции невозможно включение перехода t и он будет заведомо недостижим от любой начальной разметки сети.

Переход t  может сработать, если для него выполнены условия:

а) для "pÎ*t+ имеет место M(p)?F(p, t),

б) для "pÎ*t- имеет место M(p)<0 и |M(p)|?F(p, t).

Срабатывание перехода t приводит к изменению разметки M на M/ по правилам:

1)    если pÎt-*, то M/(p) =  M(p) – H(t, p);

2)    если pÎt+*, то M/(p) = M(p) + H(t, p);

3)    если pÎ*t-, то M/(p) = M (p) + F(p, t);

4)    если pÎ*t+, то M/(p) = M (p) – F(p, t);

5)    если pÎ *t?t*, то M/(p) = M(p).

Сети, введенные выше, назовем ПМ-сетями. Проведем сравнительный анализ выразительных способностей ПМ-сетей с известными расширениями сетей Петри. Сравним семейства формальных языков, генерируемых различными классами сетей Петри.

Будем говорить, что разметка M/ достижима из M в результате последовательности срабатываний t = t1, t2 … tk, где tiÎT, 1 ? i ? k, если существует последовательность следующих друг за другом разметок:

 или сокращенно
. Свободным языком сети N называется

L(N) = {?ÎT*|$M,

,

где T* – множество всевозможных цепочек, составленных из символов алфавита T.

Введем помечающую функцию s: T®SÈ{l}, где å – некоторый алфавит, а l – пустое слово. Функция s

легко обобщается на последовательности срабатываний gt:

Ll(N) = {s (g)|gÎL(N)} называется l-языком сети N.


Начало  Назад  Вперед



Книжный магазин