Книжка по сетям Петри (547616), страница 22
Текст из файла (страница 22)
жвство размвток М,' Я т)(И), прн которых он может сработать в И, зто те и только те разметки, которые образованы [по правилу леммь! 6.2 ! из аналогичного множвства Й; С, т) (У) . Действительно, если т может ерв ботать при разматке Ф юМ, о Мэ в макете И, то урбР Р,ЦРт.М(р)-Р(р,т)Э О. Отсюда следует, что ЧГР 6 Рр М~ (р) - Р~(р, т) > О, гдв / 1, 2. С учетом леммы 6,2 тюлучаем: 'Фр 6 Р:М(р) — Р(р, т) > О.
С другой стороны, вели т не может сработать при раз)ватке М в «7, то ен не сможет сработать при М в И, так как В р Е Р: М(р) — Р (р, т) ( О н.с учетом леммы 62,для того жар верно, чтоМ(р) -Р(р. т! ( О. В результата любой последовательности М[т,>М "[т,>... [тэ>М' прн функционировании сети >у соответствует посладоватальность М[т,>М [тт>... [гэ>М' при функционировании сети И, что гарвнти. рует справедливость утверждения леммы. П Из лемм 6.2 и 6.3 непосредственна Следует Лемме б.а.
(а) Сеть И (Иы Ит) эквивалентна макету'Ц. (б) Сеть Имаев говда и те«иго говда, ковда хв» а»квт И. Пусть 6(И,), 6(И,) — графы разметок сетей И~ и И„6(И) и 6(И)— графы разметок сетей И = (И,, Ит) и Й (см. % 1.2) . Граф 6 (Й] связан с графами 6(И,) и 6(И,) следующим образом. Пусть вспомогательный граф 64 [И) — зто граф со множеством варими В(И) = В(И,)о В(Иэ). Две вершины М и М' соединены в этом графе l-дугой (( 1, 2), ломе.
ченной символом пеРехода Г, если и только если М М, о Мз, М = М~ и Мз, вериины, Мг иМ, соединены в 6(Иг) дугой с символом г. Если г 6 Т, Й Тз, в графе 6 (Й) из вершины М в вершину М ведУт две дуги с символом т; [сдута и 2-дуга (эти дуги будем назьеать парными) . Граф 6(Й) отличается от графа 6(И) тем, что в 6(Й) отсутствуют: (а) все непарные дуги, помеченные символами из Т, Гт Т,, (б) для каждой удаленной г'-дуги — все вершины (вместе с исходящими дугами), на которые нельзя прийти из М, по l-путям, где [чтуть— зто путь по /-дугам и по тем l-дугам, которые соединяют две соседние ве[ниины.разметки с одной и той же г'.частью разметки (Т= 1, если [ = 2, и г 2,если ) 1).
(Определение графа 6(Й) неэффективно, так как все рэссматриваемью графы разметок и граф 64 (И) ыогут быть бесконечными.) На рис. бд показаны две (примитивные) сети И, ° 1((а; Ы [[д) и Из 1((с; сб аЫ. Сеть И = (И,, Ит) — это сеть не рис. б.2. Заметим, что И совпадает с И, так как Р, й Р, = ф. На зтомжерисункензображены графы 6(И, ), 6(Иэ), 6~ (И), 6(И).
Л ем ма б.б. Если разметка М' М, о Мз достижима от разметки М = М, о Мэ е сети И, то разметка М~ достижима от разметки М; е сети Ил г' 1,2. Доказательство. Если М достихммаотМв И, то в 6(И) есть путь (М, М,..., М ) . Каждое "звено" этого пути включает пару смежных верник.разметок и соединяющую их дугу. По лемме б.! в 6(И,) есть пара вершин, которые являются проекциями смежных вершин звена.
Если в 6 (Й) соединяющие дуги — это [-дуга с сиьюолом г, то, по определению графа 6(Й), в 6(И;) соответствующие верпмны соединены дугой с[а~ с'[й): Рис. 6за ° ° ь г ь а г а) ч. К пас 6.5. с тем же символом. Если эта дуга — /-дуга, то проекции смежных вершин на )У, совпадают (см. доказательство леммы 6.1) и им соответствует одна вершина в Б ()Уг ). Поэтоьгу указанному выше пути в О ()У) соответствует путь в 6(ЛГ~) отИ~ к Иг, что и доказывает утверждение леммы. П Следствием ламм 8З и 6.6 является Т е о р е м а 8З. Если е сети )У ()У„)Уз) разметка М' достижима от разметки И и переход г б Т достижим от М, то е сети Щ, ( ° 1, 2, раз- метка М 1 и переход Г достижимы отМ1.
Как в случае лемм 6.1 и 62, леммы 6З, 6.4 и теорема 6З обобщмотся на случай наложния нескольких сетей. Базовым фрагментом (Г сети Петри В, где р Е Р, называют подсеть, включающую место р, все дуги, инцидантные р, и все переходы из р О р . Например, дпя сети, показанной на рис.
6.6, а, все ее базовые фрагменты изображены на рис. 8.6, б. Регуляризоеанный базовый фрагмент (р.б.ф.)— это фрагмент, который получается из базового фрагмента следующим образом: (а) вели 'р~р' Ф (Ь. то вводится новое место, которое обычвляется головным местом р.б.ф., его развйтка полагается равной щ и из него заводятся дуги на каждый переход из 'р~ р", (б) если р"~;р Ф Д то вводится новое место, которое объявляется хвостовым местом р.бф., его разметка полагается равной 0 и на это место заводятся дуги от каждого перехода изр' ~'р; (в) если 'р~,р' = (Ь,.то р — головное место р.б.ф.; (г! если р' ~'р = Ф, то р — хвостовое место р.б.ф.
На рис. 6.6, е показаны регуляризованные базовые фрагыенты, полученнью из базовых фрагментов на рис. 6.5. 6. Р.б.ф. является регулярной сетью н р.б.ф. эквивалентен базовому фрагменту, из которого он получен. Заметим. что, асям )тл, )гр,,...., (тр — базовью фрагменты сети И и ( рь рг ° рх) ~ Р, то [Ур ю [тх ° Ъл ) а И, т.е, сеть И вЂ” результат наложания друг на друга всех базовых фрагьюнтоа, Т вора м а Вд. Класс свтвд Петри и его подкласс регулярных сетед раакомоиге», т.е. любую сеть Петри молею преобразовать а эквивалентную регулярную сеть. Д о к а з а т е л ь е т в ос Алгоритм преобразования (регулярмзации) сати состоит из трех этапов: (1) а заданной сети Патри вьщеляются вса базовые фрагменты [т'„, Рч''''' х (2) каждый базовый фрагмент [тр преобразуется в рагуляризован- ный базовый фрагмент Ур,. Рс (3) формируетея регулярнал сеть наложением друг на друга всех полу. чанных р.б.ф., т.е.
И (Ур, Ур,,..., Ур ) . На рис. В,б, а показана сеть Петри. которая не яаляатся регулярной. так как не существует задающей ее формулы, На рис. 6,6, б — вса еа базо- вые фрагменты, на рис. 63, е — соответствующие р.б.ф., на рис. 6,6, г— регулярная сеть, эквивалентная исходной сети. Построеннея сеть И эквивалентна иеходнвй сети И. Дайствитально, сеть й отличаетсл от сети й лищь тем, что а наа добавлены новые месте и дуги, соединяющие их с переходами сети И. Ясно, что те места, которые введены как хвостовые масте р.б.ф., не изменлют язык сети, так как из них на исходит ни одной дуги.
Те места, которью введены как головнью места р.б,ф„имеют разметку щ. и поэтому их добавление к входным местам сюреходоа сати И такхю не манлат язык. С) Алгебрамзеция сетей и особенно расслоение их на более простые сети позволяют более последовательно решать пробламу жмвости.
переходя от частных случаев сетей ко все более сложным. Иллюстрацией сказанного ыогут служить следующие две простыв теоремьь Теореме В,б. Регуллркек сеть й (И,,..., И„) кециев, если хотя бы одне из состаеллюилгх сетед К,,..., И„ке живе. Доказательство. Прадполохмммх противное — сеть И жива. но одна мз составляххцих сетей И, не жива, например, зе счет того, что неко- торый переход. с не достижим от некоторой разметки М' Е Я [Ис) . Так как й жива, то переход с достижим от любой разметки М Е Я[И). На осноаамии лемм 6.1, 62 и таоремы 6,6 этот переход должен бечь достихм- мым в йс от любой разметки М' Е Ю(К,), что противоречит предполо.
манию. С) Теореме 6.6 устанавливает только наобходнмыа условия живости регу- лярных сатей, Из того факта, что вса составляющие сати И,,..., И„живы, не следует, что и результирующая сеть й (й„.', й„) будет живой. Например, сати И, и й, на рис. 6.4 живы, но не являатея живой сеть И (И„К, ) [рис. 6Д) . Легко уетанавливаетея следующий факт. Т е о р а м а 6.6. Рггулярлел сеть Н (И„й,) живе, асли й, и И, жи- вы.
и пересечение их мкшкесте лгреходое еодцэжит не более одного пе- рехода. Регулярную сеть й (Р, Т, Р, Ме) назовем конечисразгцяекяод, вели НрЕР. Мо (р) Фы. Т е о р е м а 6.7. Кокечкоразмечгккая регулярягя сеть ограничена. Д о к а з а т е л ь е т в о. Пусть коначноразмеченная регулярная сеть й прадетавлана стандартно расслоенной формулой (И,, й„), Возможны даа случая. ее Если ни одна из сетей В,,..., В„не содержит мает е ы, то квхдвя иа них ограничена и, па теореме 6:2, сеть В теклю ограничена, Если некоторал составляющая есть Вг содержит маета р е разметкой МэГ(р) ы, то тогда имеетея в другой составляющей сати В( маета р е разметкой Мз (р) ~ * Ф ы.
В противном елучаа разметка ы проникла бы в сеть В; Заменим в сети Вг разметку Ме на разметку Мьн так, чтобы Мо (Р) Проделаем аналогичные изменения так. чтобы ни одна из еоетавллющих сетей не содержала мает е разМеткой ы, В силу определе. ния операции наложеннл сеть окажется представленной новой стандартно раеелоеннай формулой (В'„..., В„') такой, что ни одна иа еоетавлжащих сетей не содержит мест е разметкой щ. Эта формула эквивалентна предыдущей, а вее составляющие сети ограничены, Следовательно, сеть В также ограничена.
С) Т е ор е м а В.В. Проблема живости рэзржиима а «лаеее конах«арах. меченных рез уллрных сетей. Доказательство. Пусть В- конечнвреэмеченнал сеть, 6(В)— ае граф разметки. Для любой варшины М из графа 6 (В) вьнжшем множество Т(М) гюреходов. метящих веа дуги. исходящие из М. (У)нохаетво Т(М) содержит те переходы, которые могутерабатать ° В при разметке МЕ 0(В). Сеть В жива тогда и только тогда, когда для любого перехода г Е Т и для любой вершины М в 6(В) выполнено следующее условие: если г Е Т(М), то в 6(В) еущаетвует путь мз М в некоторую вершину М такую,что ГЕ Т(М').
В силу теоремы 6.6 сеть В ограничена. и. следовательно. граф 6(В) конечен. Поэтому можно напоередетванно убадитьея, выполнено ли для В сформулированное выше необходимое и достаточное условие живости,() э 6.3. Иерархические сати Иерархические еетм явллютея обобщением регулярных сетей н служат для модалиравамия иерархических сметем, которые, наряду е недапимыми. атомарными компонантами, содержат составные компоненты, сами представляющие собой системы (быть может, также иерархические) (9, 26) ° Для опраделенмя иарархичееких сетей и формул клаве элементарных формул, т.е.
класс символов переходов, раэбиваетея на два неперееекаю. шихся подкласса: юлминальные символы и неюрминэльныа символы. Соответственно переходы рааделяютея не лреегыа м составные. Терминальные символы и простые переходы тра«тустеп точнотакже. как и в прадыдущей главе. Нетерммнальные еммволы обозначают,"злбьмнтарную" сеть, состоящую мэ единственного составного перехода (е головным и хвостовым местом), который имеет внутраннюю структуру и является па существу самостоятельной (иерархмчаекой) сетью.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
