Питерсон Дж. - Теория сетей Петри и моделирование систем - 1984, страница 5

Запуск перехода в целом заменяет маркировку 14 сети Петри на новую маркировку 14'. Заметим также, что так как можно запустить только разрешенный переход, то при запуске перехода количество фишек в каждой позиции всегда остается неотрицательным. Запуск перехода никогда не удалит фишку, отсутствующую во входной позиции. Если какая-либо входная позиция перехода не обладает достаточным количеством фишек, то переход не разрешен и не может быть запущен.

Определение 2.1. Переход 1; в маркированной сети Петри с маркировкой 14 может быть запущен всякий раз, когда он разрешен. В результате запуска разрешенного перехода 1; образуется новая маркиРовка 14', опРеделЯемаи следУющим соотношением: Р,'(Рс) = = ФРд — МРо 1(1т)) + Ф~(Ро О(1г)). В качестве примера рассмотрим маркированную сеть Петри, изображенную па рис.

2.15. При такой маркировке разрешены только три перехода: 1„1, и 14. Переход 14 ие разрешен, так как ни позициЯ Р„ни позициЯ Ре, ЯвлЯющиесЯ входами пеРехода 14, не содержат ни одной фишки. Так как переходы 1,, 14 и 1, разрешены, любой из них может быть запущен. Если запущен переход 1,„то происходит удаление фишки из каждого входа и помещение фишки в каждый выход. При этом одна фишка удаляется из Рв, одна фишка помещается в Ре, а количество фишек в Р4 увеличивается с двух до трех. Новая маркировка, полученная в результате запуска перехода 14, показана на рис.

2.16. В маркированной сети Петри, изображенной на рис. 2.16, разРешены только переходы 1, и 1,. При запуске перехода 1, осуществляется удаление фишки из р, и помещение фишек в р2, ре и ре (в Р4 — две фишки, так как эта позиция является кратным выходом перехода 1). Эга операция образует маркировку, приведенную на Рис. 2.14. Иллюстрация того, как меняется маркировка позиций, когда запущен переход Ф). Каждая позиция может или не может бить входом либо выходом перехода.

Здесь показан случай для кратности О или 1. дз Рис. 2.15. Маркированная сеть Петри для иллюстрации правил запуска. Переходы 6, гз н Гз разрешены. Оснозньы определения рз рл рис. 2Лб. Маркировка, полученная в результате запуска перехода 1л в сети на рис. 2.18. Рис. 2.17. Маркировка, полученная при запуске перехода 6з в сети на рис. 2Лб. Рнс.

2 18. Маркировка, полученная при запуске перехода 1з в сети на Рнс. 2.17. рз Рис. 2.19. Маркированная сеть Петри. рнс. 2.17. В такой маркированной сети Петри переходы (з и гз разрешены. Запуск перехода (з образует новую маркировку (рнс. 2.18), где две фишки удалены нз рм а одна добавлена в р,. Запуски могут осуществляться до тех пор, пока существует хотя бы один разрешенный переход. Когда ие останется ни одного разрешенного перехода, выполнение прекращается.

Упражнения 1. Какие переходы разрешены в маркированной сети Петри па ркс. 2.!1, 2.12Р 2. Какая маркировка получится при запуске перехода й (рнс. 2.11)Р Какая маркировка получится прн запуске перехода га (рнс. 2.12)? Какая маркпровка получится в результате выполнения следуюшпх операций: сначала — запуск йь затем — запуск 1з (рнс. 2.12)? 3. Какие переходы разрешены в сети Патря на рве. 2.13? Какие маркировки образуются прн запуске каждого нз этих переходовР 4. Можно лк запустить переходы в сети Петри па ркс. 2,19Р Какне? 2.3. Пространство состояний сети Петри Состояние сети Петри определяется ее маркировкой.

Запуск перехода изменяет состояние сети Петри посредством изменения маркировки сети. Пространство состояний сети Петри, обладающей и позициями, есть множество всех маркировок, т„е. Й". Изменение в состоянии, вызванное запуском перехода, ойределяется функцией изменения 6, которую мы назовем функцией следующего сасглояпия.

Когда зта функция применяется к маркировке р (состоянию) н переходу 8;, она образует новую маркировку (состояние), которая получается прн запуске перехода 11 в маркировке р. Так как (? может быть запущен только в том случае, когда он разрешен, то функция 6(р, 1~) не определена, если (; не разрешен в марки- Основные определенил рокке рс Если же (~ разрешен, т о 6(р, 1,) = р,', 1 де р' есп маркировполученная в результате удаления фишек из входов (, и добавления фишек в выходы 1р Определение 2.6. Функция следу!си(ега састаяния б: Ф" )С Т -эу для сети Петри С = (Р, Т, 1, О) с маркировкой р и перехоом ~ с Т определена тогда и только тогда, когда р(р„) ~ ф~(рь у(е )) для всех р; с Р.

Если 6(р, 1~) определена, то 6(р, (,) = р', где р'(рь) = р(р~) — Ф(рг Ф~)) + 4Ф(рь 0(~~)) для всех р, Е Р. Пусть дана сеть Петри С = (Р, Т, У, О) с начальной маркировкой рв. Эта сеть может быть выполнена последовательными запусками переходов. Запуск разрешенного перехода (~ в начальной маркировке образует новую маркировку р' = 6(р', (,). В этой новой маркировке можно запустить любой другой разрешенный переход, например (д, образующий новую маркировку ра = 6(рг, у„). Этот процесс будет продолжаться до тех пор, пока в маркировке будет существовать хотя бы один разрешенный переход. Если же получена маркировка, в которой ни один переход не разрешен, то никакой переход не может быть запущен, функция следующего состояния не определена для всех переходов, и выполнение сети должно быть закончено.

При выполнении сети Петри получаются две последовательности: последовательность лсаркиравак (рв, р', ра, ...) и последовательность переходов, которые были запущены (У~а, 1;„У;,, ...). Этн две последовательности связаны следующим соотношением: 6(ра, фа) = ра+т для к = О, 1, 2, .... Имея последовательность переходов и ре, легко получить последовательность маркировок сети Петри, а имея последовательность маркировок, легко получить последовательность переходов, за исключением нескольких вырожденных случаевп. Таким образом, обе эти последовательности представляют описание выполнения сети Петри.

Пусть некоторый переход в маркировке р разрешен и, следовательно, может быть запущен. Результат запуска перехода в маркировке р есть новая маркировка р'. Говорят, что р' является непосредственна даспшжимай из маркировки р, иными словами, состояние р' непосредственно получается из состояния р. ОпРеделение 2.9.

Для сети Петри С = (Р, Т, У, О) с маркировкой р маркировка р' называется непосредственно достижимой из р,, если существует переход 1~ е Т, такой, что 6(р, 1;) = р'. Можно распространить это понятие на определение множества достижимых маркировок данной маркированной сети Петри. Если р непосредственнодостижима из р, а р" — из р', говорят, что р" 1 . о Рл~ ~б:3~ шишж~~~ а(с, н) > В оригинале вырожденные случаи ошибочно отнесены и первому утвеРасденшо. — Прим. ред. Глава 2 сети Петри С с маркировкой р как множество всех маркировок, до.

стижимых из (г. Маркировка р' принадлежит К(С, р), если суще ствует какая-либо последовательность запусков переходов, изменяющих р на р'. Отношение «достижимости»п является рефлексивным, транзитивным замыканием отношения «непосредственной достижимости». Определение 2.10. Множество достозсолгосглп К(С „) „„П ри С = (Р, Т, 1, 0) с маркировкой р есть наименьшее множество маркировок, определенных следующим образом: 1. р бК(С, р), 2.

Если р' Е К(С, р) н р" = 6(р', 12) для некоторого (у о Т, то с К(С, р). Для сети Петри, изображенной на рис. 2.20, и маркировки р, = = (1, О, 0) непосредственно достижимыми являются две маркировки: (О, 1, 0) и (1, О, 1). Из (О, 1, 0) нельзя достичь нн одной маркировки, так как ни один переход не разрешен. Из (1, О, 1) можно получить (О, 1, 1) и (1, О, 2). Пользуясь методами, разработанными в гл. 4, можно показать, что множество достнжимости К(С, р) имеет следующий вид: ((1, О, п), (О, 1„п))п ~ 0). Рг гг Рг Рг Рис.

2.20. Маркированная сеть Петри Удобно распространить функцию следукацего состояния на отображение маркировки и последовательности переходов в новую маркировку. Для последовательности переходов (1)„1(„..., 1)а) и маркировки р маркировка )г' = 6(р, 11„1(г,, 11») есть результат запусков: сначала — 1)„затем — 1(г й т д.

до 1(а. (Такая операция, конечно, возможна только в том случае, если каждый переход к моменту его запуска разрешен.) Определение 2.11. Расширенная функция следующего собтояния определяется для маркировки р и последовательности переходов а б Т"г> следУющими соотношениЯми: 6(Р, 1, о) = 6(6(Р, 1у), о), 6(р, ),)= р. Обычно мы применяем эту расширенную функцию. П Автор имеет в виду бинарное отиогаеине на множестве маркировок, такое, что (р, р') принадлежит ему тогда и талыш тогда, когда и с )с(С, р).— Прим. Ред. г> Т' — множество всех подмножеств множества (булеан) переходов T. — Прим. Ред.

31 Основные определения р2 Рис. 2.21. Маркированная сеть Петри. г5 Упражнения 1. Определите последовательность маркировок для маркированной сети Петри (рис. 2,21) и последовательности переходов 6, йн йь йь Фз. Кзк выглядит соответсгвующая последовательность переходов для последовательности маркировок (1, О, О), (О, О, 1), (О, О, О)? 2. Ранее упоминалось, что существует несколько вырожденных случаев, при которых последовательность маркировок не определяет единственную последовательность запусков переходов.

Охарактеризуйте класс сетей Петри, для которых зто возможно. 3. Покажите, что 0)г(С, р) = Фа. 1«С Фн 4. Докажите„что если )с' Е И(С, 1«), то 1?(С, р,')Я)?(С, р). 5. докажите,что н'ср(С, р) тогда и только тогда, когда )?(С, 1«') с= й(С,)«). 6. Выполняется лв равенство И(С,Р) = — 11 3(р, 11)? 1«Е Т 7. Выполняется ли равенство 1?(С, р) = () )?(С,б(М~))? Убт 8.

В некоторых публикациях по сетям Петри мвожество достнжнмости маркированной сети Петри называется ее классам маркировок. Более точно класс прямых маркировок сети Петри есть то, что мы определили как множество достижимости. Класс обратных маркировок есть множество достижимостн инверсной сети Петри (см. упражнение 9 к равд. 2.2). Тогда класс маркировок маркированной сети Петри есть объединение прямых и обратных классов маркировок.

Дайте формальное определение класса прямых маркировок, класса обратных маркировок и класса маркировок сети Петри с маркировкой 1«. Затем покажите, что классы маркировок сети Петри разбивают множество всех маркировок па непересекающиеся классы эквивалентности. Лля этого требуется показать, что отношение «иметь равные классы маркировокз является рефлексным, симметричным и транзитнвным.