Книжка по сетям Петри, страница 17

а при одном переходе в 8 лемма Формулирует достаточные условия живости этого перехода Предположим, что 8 совпадает с Т, т.е. ) Т ~ 8 ! О. Так как Т вЂ” множество всех переходов сети, то включение (8 Гтрэ (М))ь8 тривиально истинно. В силу леммы 4.1, если ни один из переходов множества 8 не может сработать, то существует пустой при Мтупик Я такой, что ЯСР'(М! 8 С Я'.

Пусть теперь 8 С Т, т.е. ! Т! 8 ) >О. Построим последовательность достижимых от М разметок М„,Мы... ..., Мс,..., М такую, что М М„и.при М имеется пустой тупик Я такой, что Я ~Р (М') и 8 ~Я'. Покажем, что все переходы множества ( 8) мертвы. Предпотюжим, что в 8 есть переход с, для которого существует входное место р в г, из которого ведет дуга на другой переход с, принадлежащий ! с), и переход с потенциально живой. по условию леммы переход с мертвый, поэтому с Е Е р'~ 8. Но тогда место р является входным для нескольких переходов, включая с и с . Так как сеть свободна, то переходы с и с имеют по одной входной дуге, и если может сработать с, то и с также может сработать, что противоречит условию.

Пусть М = Мс — текущая разметка при функционировании сети. Возможны два случая. 1) ( 8 Л Р (Мг )) ь. 8. В этом случае применима лемма 4.1. Так как все переходы из 8 мертвы, то должен существовать пустой прн Мс тупик Я = ('8 Г1 Рэ(М,) ) такой, что 8,СЯ'. Этот случай доказывает лемму при М =Мс.

2! ( 8 Г1Ре(Мг)) ф8.Тогдасуществует переход с Е ( ( 8гтР (МсИ 8, для которого возможны два подслучая. 2.1) с — мертвый переход. Это означает, что все переходы множества 8 8 О (с) мертвы. Множество Т~ 8~ содержит нэ один элемент меньше. чем множество Т~ 8. По индуктивному предположению, должна существовать последовательность срабатываний т, ведущая от разметки Мс к некоторой разметке М' такой, что для нев существует пустой при М' тупик Я ь. Рэ(СГТ) и 8 С Я'. Так кэк 8 С 8', то леммадоказанадляразметки М'и тупика Я.

2.2) с — потенциально живой переход. Пусть Мс+~ — разметка, при которой может сработать С, и М, (т ) Мс+ с. Поскольку ни один из переходов из множества ('8)' не может появиться в последовательности г, то ( 8 Г1 Р' (Мс И ь. ( 8 Гт Р' (Мс+ с! ) . Так как С срабатывает и посылает фишки в ( 8 Гтре (Мг) ), то ( 8Г)Рэ(М + ! (( ! "8л Ре(Мг)!. Пусть теперь Мь+ ! — текущая разметке. Повторяя для нев те же рассухьдения, что и длл разметки Мь, мы или приходим к подслучаю 2.2, при кото. ром мощность множества ('8 Г! Ре)Мь)) уменьшйется, или доказываем лемму, приходя к первому случаю или подслучаю 2.1. О Т е о р е м а 4.Э.

Если е свободнод сети квждььд тупик содержит размеченную ловушку, то сеть живе. Д о к а з а т ел ь ство. Из леммы 42следует,чтоеслиникакойиз тупиков свободной сети никогда на сможет стать пустым ни прн какой достижимой разметке, то никакой переход т щни не может стать мертвым ни при какой разметке. Действительно, в противндм случае достаточно взять 8 (т) и т тупиковую разметку М, применить лемму 42 и прийти к существованию пустого тупика. Таким образом, если асе тупики сети не пусты ни прн одной достижимой разметке, то все переходы сети живы. В свою оче.

редь, если тупик содержит размеченную ловушку, то он никогда не сможет стать пустым. О Теорема 4.Э устанавливает достаточные условия живости в классе сво. бодных сетей Петри; а работах (27, 41) показано, что если свободная сеть жива, то каждый ее тупик должен содержать размеченную ловушку, в про. тивном случае среди «остнжимых разметок сати существует т-тупиковая разметка для некоторого перехода т сети. Таким образом, условие таора. мы 4Э является на свмом деле наобходимым и достаточным, но мы опус. каем здесь доказательство необходимости. Проиллюстрируем применимость коитерия живости свободных сетей к примерам сетей, рассмотренных в этой главе.

В автоматной сети на рис. 4.3 (автоматнея сеть - частный случай свободной) имеются следующие тупики (исключая тривиальнььй — множило всех мест): и! (Р!. Рь. Рь). )тз (Р!.Рз) 7)ь (Р!.Рь) и следующие нетривиальные'ловушки:О, е (Р! Рь Рь). Оз (дь. Рь) как видно, ни один из этих тупиков на со. держит ловушки, поэтому сеть на рис. 4,3 не жива. В синхронизационных графах на рнс. 4.4. отличающихся лишь начальной разметкой, нетривиальные тупики: В! (Р! Р! Рь Рю Рь) Йь (Р! Рь Рь Рь) )ь (Рь Рь Рь Рь) Дч ~(рч,рь,рь). ))ь (Рь,рь,рь). 7)ь (Рь,рз) ))ь (Рь,рь), 7)з ~(рь,рь). нетривиельныа ловушки: О! (Р! Р!.Рь.рь Рь).

Ог (Р! Рь.рь.рь). Оь (Рь.рь,Рь.рь). 0,-(р,,р,,р,). 0,-(р,,р,,р,», 0,-(р,,р,'), Ог (Рь. Рь). Оз (Рь, Рь) ° Любой тупик в обеих сетях содержит ловушку. В сети на рис. 44;б все ловушки размечены, поэтому эта сеть — живая. В сети на рис. 4Ае тупик ( Рь. Рь ) содержит ловушку От ~ (Рь, Рь), но зта ловушка не ссдар. жит фишек, поэтому сеть на рис.4.4,в не является живой. В синхрографе на рис. 4 б каищый из туяикое (Р!. Рз) . (Ра. Рь) . (Рь. Рч.

Рь! ссдерхьнт раз!!а. ченную ловушку ( р,. р ) или ', рь. Рь ). В свободной сети на рнс. 4 7 нетривиальные тупики: (Р!.Рь.Ра,рь.рь). ь)ь (Р! Рь Рь.рь Рь) Дь (Р!,Рь,рь,рь) ° ь)ь (Рю.рь~рь) ° г)ь (Рь.рь) ° нетривиальные ловушки: О, -(р,,рэ,ра,р,,р,), О, - (р„р .р .р .р.). аэ-(р,,рэ,р,,р,), а,-(р,,р,,р,), а,-(р,,р,).

Все ловушки размечены, но тупики (га и т1, не содержат ни одну из ло. вушек сети, поэтому сеть на рис. 4.7 не является живой. Действительно, последовательность СРабатываний Гэ тат, Гэ пРиводит к тУпиковой Разметке (0,2, 1,0,0, 0) . Заметим, что условия живости для автоматных сетей и синхрографов могут быть получены из теоремы 4.10 как следствия. Условия безопасности для свободных сетей Петри будем выводить только для живых сетей. Для живых свободных сетей Петри имеются необходимые и достаточные условия их безопасности, формулируемые без привлечения графов разметок.

В сети Петри (Р, Т, Р, Ме) замкнутой подсетью, задаваемой подмножест. вом мает 0 С Р, называется сеть (О, Т', Р ', Ме), в которой Т' "0 Г1 0', Р Р Г1 (О Х Т (Э Т Х О), Ме Ме(0) . Другими словами, замкнутая под. сеть. задаваемая подмножеством мест О, включает места из О, все переходы, инцидентные ~0, и все дуги, связывающие 0 и Т, а начальная разметка подсети является проекцией начальной разметки сети на маета из О.

Например. в сети на рис. 4.8,в замкнутая подсеть, задаваемая множеством мест (рыра), выглядит так, как показано нв рис.4.8,б, а замкнутая подсеть, задаваемая множеством мест (рэ, р з), показана на рис. 4.8, в. Будем говорить, что сеть Петри покрыта заданной совокупностью замкнутых подсетей, если каждое место сети входит в одну из подсетей этой совокупности. Соответствующая совокугность подсетей покрывает сеть. Например, подсети на рис. 4я,б ив покрывают сеть на рис. 4.4,а. Критерий безопасности живой свободной сети связан с покрытием ее замкнутыми подсетями, которые представляют собой сильно связные автоматные сети, каждая из которых содержит лишь одну фишку.

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

Еслибы зтобылонвтак, то вернув в полученную живую сеть одну фишку в то же самое место, мы получили бы, как легко видеть, небезопасную сеть. П Л е м м а 4.4. В живой набазопасной свободной сати сушестаует наограяичвииов Ямато. До к а з а т ел ь с т в о. Изтеоремы4.9спедует, чтоаслиизменитьначальную разметку сети, удовлетворяющей условию данной теорамы, удалив из сети все фишки, кроме фишек в ловушках, то полученная вать останется живой. Пусть сеть работает до тах пор, пока одно из мост не получит два фишки (асли при Ма не было таких мест) . В каждом месте, в котором больше одной фишки, поматим каким-либо образом (например, закрасим в красный цвет) вса фишки, кроме одной.

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