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

процесс совпадают. В качестве первого примера преобразования развертки рассмотрим развертку примитивных сетей (см. % 6.11, которые прийадлежат пересечению класса автоматных сетей (% 4.21 н регулярных сетей (й ВЯ1. На. помним, что простой путь а сати представляет собой последовательность элементов сети («,, «ы..., «„1 такую, что клс«м~ для всех 1 Ю < пи «г чь «для любых двух элементов сети. кроме, быть может, «, и «„. Про. стой йуть называется простым циклом, юли «~ ~ «„. Простой цикл назовем резулярным, если «, и х„- головные и хвостовью места в циклической подсети примитивной сети, т.е. в подсетй, для всех элементов «, у которой верно, что «Р'у Л уР'«.

Назовем чик«очес«ми компонентом примитивной сети Д( ее максимапь. ную циклическую подсеть Э' такую, что ~Фу Е Х~Х, В «ЕХ: 1(«Е'уЛ уР+«1. И7 Пюбой циклический компонент праастааим в аиде формулы сети, начи. иающейсл операцией ите«пцни», Максимальная подсеть сети Н, не солержащея внутри ни одною цикли. ческого компонента. обрезует аачткличаскмд ксмлснаиг.

Пагко сипеть, что любую примитивную сеть И можно прелставить как коначную чералующуюся последовательность циклических н ациклнческих компонентов; И (Нг,Нз)...,И„),глен»1,идлллюбого! Ю (и, если Иг- циклический (ациклический) компонент, то Им~ - ацикличаский (циклический) компонент, Пусть Н «Р, Т, Р, Ма) — исхолная сеть Петри; условимся в порожааемой сетиччроцессе И" (Р, Т, Р, Ме) использовать ° качестве злементов мно. жестаа л Р 0 3'символы мюментов нз Х Р 0 Тс дополнительными аерхнимн ннлексами. рассмотрим развертку примитивной сети со стандартной нещльной разматкой Ме, при которой только ааинственное головное место расти имеет разметку Ме(р) 1. е остальные места имеют нулевую разметку. На рис, 7,10, а показана примнтианея сеть И 1е; » (л; »с; т«); е, на рис. 7,10, б сеть прелставлена как комбинация компонентов (Н,; И„Из), где И~ и Из - ациклнчаские компоненты. Из ° (Ь; »с; гб-циклический комгюнент. Прн развертке текой примитивной сети сначала отдельно разворачивают» сл все ее циклические компоненты, В каждом циклическом компоненте И~ имеетсл елинственное головное (и хвостовое) место Рг (в компоненте Из на рис.

ТЛ О, б такое место — место Рт1. Головному месту Р~ компонента Нг сопоставляется головное место р) развернутой сети Ц . Дюже развертка осущесталлетсл инлуктнвным саюсобом. Пусть р - некоторое место в компсненте И» и ему соответствует мееМ р» ° построенной части сети И», причем /- макснмапьный индекс среди верхних индексов копий месте р а построенной чести И,. Если р' ~ (г»,... ..., г„)в И», то в И» добавпл»ется вераинь»ч»ареходь» г»»» ~ (есин нк еще нет а Й»1 и иэ месте р» заводится дуги на кеждь»й нз ноаык добевпенных переходов. Пусть с - некоторый переход ° цикпнческом компонанте И» и ему со.

ответствует а построенной части сети Й» перекоп г». где»' — максимапьный верхнйз индакс среди верхних индексов копий переходе г в построенной части Й», Здесь возможны дае продолжения развертки, 11 Если место о ° г ' не яаллетсп головным местом некоторого регуплр. ного цикле а И», то просматривается построенная часть Й» в поисках места о . Есяи текое место найдено, то оно объпапяется вь»хойнь»м местом пере. кода г', ° противном случае добааппетсл новое место»7» с верхним индек.

сом/ и не наго заводится дуга от парекода г», 2) Еспи место а ~ г' явллетсп гопоаным местом некоторого регупнрного цикла а И», содаржащего с, то просматривеетсп построенная честь Й» ° пома. кем месте о»". Еепи таков место найде»о, то оно обьявяпется выж»бным местом перепаде г». ° противном спучае добаеппется новое место ф~+» и на него заводится дуга от перехода г». На рис. 7.10, е показана развертке»у» циклического компонента Из се. тн И, изображенной на рис. 7 10.е. После развертки отдельных цикпическнх компонентов осуществппетсп нх стыковке с ациклнческнмн компонентами, если таковые импотся в исходной сети, Пусть И ~ (И»,' Ит,'...,' И„!, Дпа стыковки И» и Й»+» а том случае, когда И» - ацнкпнческий компойент, а И», » — развертка цикпичес.

кого компонента, выделяется единственное общее "стыковочное" место»з, которое яйпяется хвостовым местом в И» и головным в И», », н зетам р ° И» н р' в Щ+» спивпотсп. Дпл стыковки Й» с И», » в том спучее, когда Й» — развертка цикпическо. го компонента, а И»+» — ецнкличаскнй компонент, выдвинется стыковоч. нос место»з, котгрое является хвостовым местом в И» н гопоаным в И»+» . После рзеаарткн цнкпического компонента И» а ецикяическу»о сага'Й» зто.

му месту»з в й» соответствует бм»конечнеп поеледоаатепы»ость квостовь»х мает р', »зт,... Прп сть»коека И» с И»„головное место р из И„, резко. пируетсп в бесконечную последовательность»т», р'..., вместе с еыкодны. мн дугами, пераходаьм, на которь»е зти дуги ведут, и аь»ноднь»ми дугами этих пепеходоа, »к»спе чего спивается одинаковые копии мест р', р' „.. из Й» н из»Ч», », где И»ч» — это ацикпический фрагмент после копировайип его головного места. Нз рис. 7.10, г юказзна 8 сеть Ю, гпядстеаяяющея процесс функциони. ровения пйимитнаной сети И. изображенной на рис, 7.10, е, Лагко видеть, что 8 сеть И не явпяетсп».

ч»потной, так как ° ней имеется Псечение ( р ы е, рь ь», р~, »»», г»~, ьт, »»~, »1', р1,... ), которое не пересекаетсл с а» сечением (еы ез, ез ° ° .) . поэтому исходная примитивная сеть и ю1 °;«Ег; 'с;я ° не лвпяатся 1. ч»яотнай. Процедуре развертки примитивной сети со стандартной разметкой сао.

питая, как легко видеть, к выдепанин» асах возможных путай в графе исходной сети и скпенамаао путей ° тех местах, песне которых эти пути совяаде»ст, Поэтому сярзаепянаосяадуницее утверждение: Т е о р е м а 7Д. газ»»легатом»п»зее»эгк»» п»»т»н»»ппнай сети со егпчдергнад печальной резмегк ч7 яа»»пегая Зсеи. Пусть [[) -исеть, полученная разверткой примитивной сети )У со стан.

дартной начальной разметкой. Если для йг ввести помечающую функцию Х такую,что Х[г«) гдпя любого у,где 1[Я )г,ге 7; то можно сформулировать следующую теорему. Т во рема 7Э. [.[)У) = [. ()У, Х), тхь свободный прсфиксный язык сети Ми префиксный язык помеченной сети [)У, Х) совпадают. Развертка примитивной сети с произвольной начальной разметкой осущаствпяатся сваданием к рассмотренному выше случаю сети ео стандарт.

ной начапынн«разметкой. С этой цепью яронзводнтся ярвдваритепьное преобразование расщепления исходной сати на совокупность примитивных сетей со стандартной разметкой. Расщепление осуществляется следующим обрезом. Пусть т — сумма фищек в начальной разметке исходной сати. Если тп О, то сеть порождает "пустой" процесс, никак.на иэобрежаамый сетями, В противном случае эта сеть копируется в гп экземплярах, и каждый иэ акземппяров сети получает новую начальную разметку по спедующв. му правилу: 1) в каждой копии единственное место имеет ненулевую разметку, равную 1; 2) если место р в некоторой копии имеет фищку, то Мс [р) ) О в исходной сати; 3) общее число копий, имеющих фищку в маете р, в точности равно Мс (р) в исходной сети.

Следующий щаг состоит в индексации пареходов и ммп в каждом из гп экземпляров, Эти экземпляры упорядочиваются произвольным образом и каждый элемент Дго экземпляра (1 С ) 4 т) получает верхний индекс [. На рис, 7.11, а показана примитивная сеть 2а; «[и;1с). Начальная разметка этой сети [2, О, 1) отличается от стандартной. На рис. 7.11, б исходная сеть преобразована в совокупность трах примитивных сетей. две из которых рг р« ЫРс) ф+-Я; см чя сы Ьы см з) тмс. 7,11. имеют по фишка в головном масте, а третья содержит фишку во "внутреннем" маете рэ.

Каждая из копий резаорэчивеатея по правилам развертки примитивной сети со стандартной разметкой, причем переходы и маета получают второй верхний индекс. В случае, если в некоторой копии фишка содаржится не в головном маете сети, как, нащжмер, в третьей копни сети на рис. 7Л1, 6, развертка осуществляется, как будто фишка находится в головном маета Затем фишка помещаетел в первое вхождение р~' (в развертку копии) того места р', которое сода(хншш фишку в соответствующей и)) копии исходной сети, Наконац, в развартке М копии удаляютея все те элементы х (и связывающна их дуги), для которых не вьаолняется отношение р~' Р х, т.е.

те элементы, которые не достижимы в рааварнутой сети при движении от места р" вдоль дуг сети. При этом необходима корректировка вторых верхних индексов оставшихся эламентов. Для элФмента хЧ берегся новый второй индекс Ц - х), гда х — максимальный индекс удаленного элементе х'". На рис. 7,11, е показана сать. получаннал в результате развертки сети на рнс. 7.11, а, Заметим, что развартка примитивной сети с произвольной началыюй раз.

меткой может привести к сети, не являющейся 8 сетью, т,е. теорема 73 не верна дпя этого елучея. Например, сеть на рис. 7.11, е ляпнется Д-сетью. Для получаемых сетей.процессов выполняетея ограничение А10 (см. % 7.З), т.е. каждый переход имеет ровно одну входную и ровно одну вьпюдную дуги, но нарушаетел требование АВ к 8 сати имать ровно одно головное место.