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