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

1з, достаточно проверить равенство языков 1з = 1з, где 1э = 1, [1 1з. Отсюда следует, что проблема эквивалентности языков сетей Петри [классы Х,Хь,Ха,Хьо) неразрешима. С) В табл. 3.1 суммированы сведения о разрешимых (Р) и неразрешимых (Н) свойствах классов языков сетей Петри, а также о свойствах, к анализу которых может быть сведена проблема достижммости (С) .

52 Тааанча 3.1 Проблемы Экенаалантксстн н аключеннл Пустоты н канаенастн Ппнналлежнсстн Классы леыкс Р Р Р с с сл Р Р с С Н и и и Энс. ЗЛО. Рассмотрим, как сильно локальные изменения в структуре сетей Петри влияют на порождаемые ими языки. Следующие теоремы говорят о том, что такие "малые" изменения, как удаление одного перехода или одной фишки из сети, приводят к нераспознаваемым измемениям в порождаемых языках. Т е о р е м а 3.1 б. Неразрешимой является про бпел(д изменится пи пре- фиксяый или терминальный язык сети, если из яее удаяита .некоторый переход. Д о к а з а т е л ь с т в о. Пусть сеть )У имват вид, показанный на рмс.3.10,а, гда й(, и (уэ — ае подсети, каждан из которых представлена в стандартной форме со специальными включающими местами оп, и опз, не содержащи.

ми, однако, фишек. Место оп является "включающим" местом в сети В, переходы с ~ и та помечемы одним и тем же символом а, который не может помечать переходы подсетей Р), и Д(з. Обозначим через (. префиксмый язык ~()у, Х),через (.г -язык (. (Вг, Х), где / = 1, 2, через (. е — терминальный язык Е ((У, Х, Му) для некоторой тер. минальной разметки МР через баг — язык 1()уг, Х,Мг(рг) ),гдерг — мно. жество мест подсети (ч, ! 1, 2.

Имеют место очевидные равенства: ((. 1зсэ)О(Л). б а ((.с, О(. ). (Считаем, что начальная разметка Ма сети й( не выбирается в качестве тер- минальной разметки Му.) Пусть (. и Ла обозначают прафиксным и терминальный языки сети, полученной удалением из сети д(перехода тэ вместе с мнцидемтными дуга- ми. Тогда, (.' = а с (е О( Л). (е = а с (е ы Из этих равенств следует,что ( =( о~э С(ы (а ба ' "(еэ С(еы Следовательно, предположение о разрешимости сформулированной в творе. ме проблемы приводит к разрешимости проблемы тт.включения для язы. ков из классов Х и Хс, что противоречит прадыдущей теореме. П Т е о р в м а 3.16. тйгрвзрвшимой является проблема, изменится ли лрефиксный или терминальный язык сети, если иэ некотором ее места уделить фшику.

Д о к а з а т е л ь с т во. Пустьсеть Фнарис.3.10,6отличается от сети, рассмотренной в доказательстве предыдущей теоремы !рис. 3.10,в1, лишь тем, что в нее добавлены еще один переход та, в который ведет дуга из ыеста оп и из которого ведет дуга на "включающее" место подсети Иг, и еще одно место р, из которого заведены дуги на переходы тг и гг.

Новый переход помечен тем же символом д Сеть 1У будет отличаться от сети 1У лишь начальной разметкой; в которой место р не имеет фишки. Пусть Е и Ев обозначает соответственно префиксный и терминальный языки сети М . Тогда Е в«(Ег ОЕг1О(М. Ее в«(Ее~ ОЕог1 в«Е, О(Х~, Е е«Е,. Вновь, как и в предыдущем теореме, имеем Е Е ' «'Ег ыЕг. Ее Ее ЕегыЕег ° откуда следует неразрешимость сформулированной в теореме проблемы. С1 ГЛАВА 4 ПОДКЛАССЫ СЕТЕЙ ПЕТРИ Сети Петри моделируют широкий спектр дискретных систем (с учетом теоремы 3.7), но для некоторых распространенных специальных классов систем удобно применять сети Петри не общего вида, а некоторые их подклассы, более простые и более адекватные рассматриваемым системам.

Кроме того, проблемы анализа свойств сетей общего виде оказываются или неразрешимыми или достаточно сложными. Поэтому вводились и исследовались различные подклассы сетей Петри, получаемые в основном путем упрощения топологии (трафовой структуры) сетей; некоторые из этих подклассов рассматриваются в этой главе. 5 4.1. 0)ивщарвые сети Петри В определении сети Петри (см. % 1.2) присутствует функция гУ, задающая кратность дуг, и для срабатывания перехода г при функционировании сети требуется, чтобы каждое его входное место р имело разметку не меньшую, чем кратность дуги, соединяющей р и с, а после срабатывания перехода г разметка любого его выходного места о увеличивается на кратность дуги, соединяющей с и о.

В общем случае кратность дуги может быть любым неотрицательным числом, но если все дуги имеют одну и ту же кратность 1, то сеть относится к подклассу ординарных сетей. Для срабатывания перехода в ординарной сети Петри требуется, чтобы каждое его входное место содержало хотя бы одну фишку, а после срабатывания перехода квкдое его выходное место получает дополнительно по одной фишке. Наличие в сетях Патри дуг с кратностью, большей единицы, позволяет естественно моделировать реальные дискретные системы, но во многих случаях теоретического анализа сетей удобней ограничиться рассмотрением ординарных сетей. Возникает вопрос, насколько переносимы результаты, полученные для ординарных сетей, на общий случай сетей. Хак [43) показал,что подкласс ординарных сетей не является существенным сужанием класра сетей Петри и по отношению к большинству своих сетей оба класса оказываются эквивалентными в том смысле, что для сети Петри с заданным набором свойств можно посроить срдимдзную сеть, абладающую тем же набором свойств.

Предложенное Хаком преобразование произвольной сети Петри )У ~ (Р, Т,Р,И',Ма) вординарнуюсеть(У (Р, Т,Р,ДГе) состоит в следующем. 1) Для каждого места р б Р определяется максимальная кратность и (о» дуг, инцидентных этому месту, по формуле п(р) птах (Р(р, Г) + Р(г,р!). тя г Так,для места р нерио.43,а п(р) =3. о) 2) Каждому месту Р Е Р будет соответствовать в сети ЛГ' множество Р' (Р» из и (Р) мест р',р',...,Ро(р), где п (Р) — определенная выше максимальная кратность дуг дпя места Р.

Таким образом, общее число мест в Р равно сумме максимапьных кратностей дпя всех мест из Р, т.е. Р' = О Р'()з!. р яр 3) Каждому переходу ГЕ Т соответствует в Т единственб) ный переход, обозначаемый тем же символом г, но в сети )у Рнс. 4Л. появляется также множест- во Т (Р! = (гн гы ° ° ° ° го(р) ! новых переходов, которыесвязывают мостар',Р',..., Ро(р) из множества Р (Р) в кольцевую сеть, как показано на рис. 4.1,б. При этом, если п(Р)= = 1,то новыепереходы невводятся.узким образомТ = То( )) Т (РП.

рддр 4) Для каждой дуги сети Л( связывающей место Р с некоторым переходом с и имеющей кратность гу(р, г), заводятся )у(р, г) дуг, связывающих г с местами р', Р,..., р (Р) . При этом распределение дуг в сети )У по местам р', Р',..., Р" (Р) произвольно, лишь бы не возникали ситуации, когда переход и место связаны более чем одной дугой. На рис. 4.1,е показано распределение дуг в простой сети, построенной по сети на рис. 4.1~е. Начальная разметка Мо (Р) места Р' Е Р'(Р) в сети Л) определяется следующим образом: Мо (Р ) Мо(Р), Мо (Р ) 0 дпЯ l > 1. Анализ способа, которым конструируется ординарная сеть Л( по сати Л), позволяет установить связь между свободными языками ~ (Л)) и (. (Л) ] обеих сетей и множествами достижимых разметок Я (ЛГ] и Я(Л)').

В копьцевой подсети ординарной сети Л), образованной множеством мест Р (Р) и множеством переходов Т (Р), фишки могут беспрепятственно перемещаться по местам и распределяться в них произвольным образом, если срабатывают только переходы из Т (р), причем сумма фишек в местах из множества Р (Р) остается постОянной.

Если в сети Л( переход г е Т может сработать при разметке М Е Я (Лl), то переход г Е Т Г) Т может сработать в сети Л) при разметке М Е Я(Л) ) такой,что 'оРЕ г: Х М'(р')=М(Р!. р' и Р'(р) Таким образом, можно утверждать, что если г — последовательность срабатываний из (. (Л)'], то ее проекция на Т (см. % 1.2) явпяется поспедоватепьностью срабатываний из Е(Л)), а для любой достижимой в сети Л) раз- метки М Е Я(И ) существует разметка Мб В(И) такая, что т(рЕР: М(р) 2' М (р ).

л' и г'(л) Т е о р е м а 4.1. Описанное преобсвзоеаиив сетвд lЬгри е ординарные саги Петри сохраняет основные сеодсгеа исходных сетад — живость, огра. ничеяяосгь,консервативность. Д о к а з а т е л ь с т в о. Поскольку язык й (И) состоит нз последомтельностей срабатываний, являющихся проекциями последовательностей срабатьнмний из Е (И ) на Т, то в ординарной сети И любой переход г. принадлежащий Т й Т, является живым тогда и только тогда, когда (в живой в сети И. Если все переходы из Т й Т живы в И, то и все "новые" переходы в И, принадлежащие множеству (.) Т (р), живы в силу ря л устройства кольцевых подсетей, образованных местами из Р (р) и переходами из 7 (Р) . Таким образом, ординарная сеть Петри И жива тогда и только тогда, когда жива исходная сеть Петри И.