Книжка по сетям Петри (547616), страница 25
Текст из файла (страница 25)
Т в о р е м а ВЛ2. Ямелюбодпцсиподобнмхсагед И, Е8, и И; Ебз верно: Е(Иь) 2 Ь(Из ), аде Ь (И) — пслныб саободяыд язык иерархической саги И. за Д о к а з а т е л ь с т а о. Любой а переход 'г, который макет стать активным в Ит при начальной раз. метке Ме, может стать активным и в И, яри Мь, так как различие между сетями из 81 и из 81 селза. но только с условиями завершения составных партисдов. Начальная разметка Мч сменится на одну и ту же разметку М, в сбоях сетях, потому что топология сетей И, и Ит ОдинВкова.
СВВйюаательно, Апя шобой посладовательности срабаты- рнс. В.10. ваннй г Гы Гт. °... Г„из Ь (Иг) варно. что г, Е ТТ является и первым символом некоторой последовательности г е ь (и~ ) . индукцией по длине последовательностей из ь (ит) лагко устанавливается, что в Ь [И, ) существует г" г. В то жа арами в Е(И, ) могут существовать последовательности срабатываний, которые не входят в Ь(И, ). Они аозникаот в том случае, когда некоторый составной переход может завершиться в И,, послать фишки в свои выходные маета и тем самым активнровать другие переходы, а в Ит этот переход не можат завершитьсл, так как ожидает появления фишак в сторонних местах. Например, для подобных сетей И1 и Ит со структурой сети, изображенной на рнс.
6.10, соответствующие языки имеют вид: Ь(И, ) ',а, й вй, ив, йаЬ, «ВЬ, йаЬо, айЬй, йаЬйс, айЬйс, йй, ййа, ййс, ййас, ййса), Ь(И,» * (э, й, ей, йа, йаЬ, ейЬ, йаЬО, эйЬй, йаЬйс, айЬнс). Эдесь й обозначает активнрование составного перехода и а Π— его за. вершение. С) Т е о р е м а 6.13. Любую иерархическую сеть с оэпл)алием иэ 8т меж ко преобразовать е Х-экеиеэлэкгкую сеть иэ классе 81.
Д о к а з а т ел ьс тв о. Достаточное каждь1й составной переход н до. бавнть Х-переходы д1, дт,..., гг„по одному на каждый Охватываемый переходом и пераход г,,..., г„, имеющий хотя бы одно внешнее входное место. Входными и Одновременно выходными местами Хчюрвхода тг1 Наэначаютеп ЛОкапЬныа вхоДныа места пеРЕХОДВ Гл 1<г'<гь Перв- ходы д,,..., б„не позволяют завершиться составному переходу и в построенной сети, пока для всех них не окажутся ложными условия активации, которые совпадмот с лбкальиыми условиями активацтйг ПЕРеходов 'г,,..., г„. с) На рнс, 6.11,а показан пример составного перехода сети с ожИданием, а на рис.
6,11, б — фрагмент Х-эквивалентной сети из класса 8, . Т е о р е м а 6.14, ЛРомэеолькую Окаобигоркую сета можно преобразовать е Х-экеивэлвнпгую гмрдохищскую сеть с ожидюпгяи иэ клюев 81. Д о к ° з а т е л ь с т в о. Преобразование осуществляется а три этапа. На первом этапе ингибнторнал сеть преобрезуется ° Х эквивалентную ингибиторную сеть, обладающую сведукяцнм свойством: любой переход сети содержит среди своих входных и выходных мест не более одного ьмста, из которого исходит ингибиторнал дуга.
На порем этапе полученная ингнбиторная сеть представляется как результат наложения базовых фрагментов УР,, »гР,..., УРч, где (Р3, Рт,. ° °,Рь) — мнох1естВО всех мест Фт э ввлт. сети. Дпя каждого фрагмента ингибиторной сети строится Х-экеивапентный фрагмент сети с охощанием. Наконец, третий этап состоит ° сборке иско.
мой сети из классе Вз с помощью операции наложения. ! й з т а и. Исходная сеть преобразуется ° Ьэквивиюнтную ннгибиторную сеть таким обрезом, чтобы никакая пара безовьж фрагментов второй сети не содержала один и тот же гюреход. Если ни один переход исходной сети не содержит среди своих входных и выходных мест более одного места, инцндантного ннгибиторной дуге, то она остается без изменений. В противном спучае дпя каждого переход ° а, на удовпетворяющаго выщепрнвцаенному требовамю, добевпяатся Х переход т, допопнитепьнне места с некоторой разметкой н дуги,. соединяющие зти места с переходами сети, Чиано допопнитепьных мест и конфигурация новых связей зависят от того, как связан пережщ с маетами, инцндентнымн ингибиторным дугам (нюовем такие места ингибиторными) .
а) Пусть переход а имеет два входных ингнбиторных места (см. пример на рис. 6.12, а) . Добавпяются четыре места (масте Ры Рт, Ры Рч на рис. 6.12, б) . Первые два места лвпяются копиями двух ингибнторных мест, имеют ту же разметку и в них заводятся новые дуги от тах переходов, от которых ведут дуги в ингибиторнью места. Из одного нового места зево.
дится дуга на переход а, из другого - г,. Два других места связывается ДУГаМВ С ПаРЕХОДаын а И Г„таК, КаК ПОКаЗаНО На РИС. 6.12, б, И В ММГГОРз помещается фищка Зги два места разрещают переходам а и т, работать топько поочередно, Можно напосредртвенно убедиться, что текое преобразовение приводит к Ьэкаивелентной сети. Преобрезованне легко обоб. щеется на случай бопае двух входных ингибиторных мест. б) Пусть переход а имеет вход. Ф нос Р~ и выходное Р, ингибитор. ные места (см. пример на рис. 6.13. а) .
В этом случае добавляются два допопннтепьных места г а, Рз н Рч и допопнитепьныа дуги. д д Места рз н Рч игреют ту же роль, В д что н одноименные маета в пре дыдущем случае. Кроме того, и." Ь з места Рч завоДитсЯ ДУга не пеРе ходы, связанные ингибиторнь~ми Э' ~ дугами с местом Рз. Непичие етой а) г г) г дуги не разращаат этим переходам сработать в том спучае, когда мес. эчь в.12. то рт имеет нулевую резметку, а) знп вяз. переход а сработал, а Х-переход г~ еще не сработал и нв поместил фищку' а место рт ° а1 В случае, асин а имавт даа выходных ингибиторных маета, добав. ляется места рз, рч и дуги заводятся так же, как н а предыдущем случае. Дуга, ведущая иве на одно из мест, "передается" Х-переходу г~. Остальные случаи наличия нескольких ингибиторных мест у перахода е представляются как комбинецин рассмотренных случаев, и посладоаательно лрнменямтся описанные преобразования.
Во асах случелх. если переход а имеет среди своих входных мест таков место р, на которов на валет ни одна дуга, то к атому месту присоединяется Х.переход с одним вход. ным местом р, Начальная разметка места р становится нулевой,вместо р' получает разметку маета р. Это необходимо для того. чтобы на последующих этапах мвсто р стало анвщннм местом дяя составного перехода. содержащего переход д 2.6 з т а и. Построенная на первом этапа ингибнторная сеть представ. лнетсл как результвт наложения вв базовых фрагмвнтоа.
Есяи базовый фрагмент не содержит ннгибнторных дуг, то этот фрагмент объявляется б~ изменений фрагментом сети нэ класса 8т. В противном случае базовый фрагмент Ул (рис. 6.14, е) преобразуется ао фрагмент Иа иерархической сети с ожиденивм так, квк показано не рнс. 6.14, а (число переходоа, связанных с местом р дугами одного типа, несущвстаенно1. Фрагмент ЭУ~ со. стоит нз двух составных мрвходов, отлнчпощнхся разметкой внутренних мест р и р', места ре и перехода с.
Месту р а Мр соответствуют Фрп месте р, р' и де а ЭУ„. В месте ре фищка может появиться, только вели разметка мест р или р' становится нулевой. Наличие двум составных переходоа одинаковой структуры вызвано твм фактом, что а составном парехадв начальная разметка вго внутренних мест восстанавливается после зааврщения перехода.
Если место р в У„ ъч, вле. имеет нанулавую разметку т, то посла завершения перехода и, т.а. поела того как место р, лишится всех фишек, разметка гл в нам восстановится. Поэтому вместо перехода и следующий раз начнат работать пароход г, в котором месте р'. аналогичное маету р, на содэржит фишек. (Заметим, что зепи р в гр ммаат ~(улавую разметку, составной параход г можйо злиминировать в )ур,) Зй э т а п.
Осуществляется наложение фрагментов сети из класса За, построанмых по веем базовым фрагмамтам промежуточной ингибиторной сети. Затем для каждого фрагмента ИГр из любого анашнаго маета, связанного дугами с шцюходами а и Ь в составном палахода и, заводятся такие жа ДУГИ Дяя Ла(ааХОДОВ Гт Н Гз В СОЕТЗВНОМ Па(юкода Г. ОлимаКОВЬЮ Мат ки переходов элиминируются методом, опмеанным в работа [43).
и проводится рагуляризацмя сати. Праюбразоааниа исходной ингибиюрной сети в иерархическую сеть с ожиданием завершено. Я Т а о р а м а 6.16. Класс Зт иврррхичвских свгвй с шхиданивм рввномошвн классу 8, иврврхичвских сагой, классу ингибигорных сетей и классу сваей с ланкаеигвгами. Он строго мощжвв классе мтвд Патри и класса рвау-' азтрных свгвд. Д о к а з а т а л ь е т в о. Из теоремы 6.13 следует, что класс 81 мощнее класса 8,. Ранее было показано (теорема 6.11), что класс 8, равномощан классу ингибмторных сагам и сетей с приоритетами. Теорема 6.14 говорит о том, что класс 8, мощнее класса ингибиторных сетей.
Отсюда слвдуат, что веа эти классы сетей равномощны. 'Тот факт. что класс свтай с охмдамиам строго мощнее классов еатай Патри и рагулярпых сачей, напосрадетванно слццуат из теоремы 6.11. С) Запретив иепользованиа в иерархических сетях мест, которые являются внешними для внутренних переходов составных переходов, можно выдллить класс иарархичаских сатай 8ы который образует собственный подкласс как класса З„так и класса 3,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
