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

Тот факт, что сеть И ограничена (консервативна) тогда и только тогда, когда исходная сеть И ограничена (консервативна), непосредственно еле. дует из установленной выше связи между достижимыми разметками в множествах Я (И) и Я(И ) . Р Если исходная сеть Петри помечала символами из некоторого алфавита А, то описанное преобразование позволяет получить помеченную ординарную сеть Петри, порождающую те же префиксный и терминальный языки, что и исходная сеть.

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

Это означает, что класс всех префиксных языков ординарных помеченных сетей с Л-переходами совпадает с классом Ю~ префиксных языков сетей Петри, а класс терминальных языков ординарных помеченных сетей с Хчюреходами совпадает с классом Хе~ терминальных языков сетей ПеФри.

Предлагаемре преобразование приводит в общем случае к тому, что помеченная сеть без Х.переходов преобразуется в ординарную помеченную сеть, содержащую Х-переходы. Теорема 3.3 говорит о невозможности избавиться в общем случае от Х.переходов, и, следовательно, не ясно. можно ли помеченную сеть Петри без Х-переходов преобразовать в ординарную помеченную сеть без Х-переходов. Однако в другой работе (44) Хак предложил новое преобразование, результатом применения которого к сети без Х-переходов являетсл ординарная помеченная сеть (в общем случае также с Х-переходами), которую можно преобразовать в эквивалентную сеть без Л-переходов.

Таким образом, для любой помеченной сети Петри без Х.переходов существует эквивалентная ей помеченная ординарнал сеть без Х-переходов. т.е. классы 57 п(юфиксмых и минапьных языков орлика)змых сатйй без 1 па(хжодов совпадают соотве отвеине с классами Ю и Хе. Обсужденные факты позволяют сформулиро ть следующую таораму. Т е о р е м а 4.. Ординврнью сети Петри генерируют те мэ классы языков Х, Хе, Х~, Хео, что и сети ПвтРи с кРатными дУгааси. Если класс помеченных ординарных сетей равномощеи классу помеченных сетей с кратными дугами по отношению к префиксным и терминальным языкам, то иная ситуация складывается со свободными языками.

Т е о р е м а 4.3. Клесс свободных языков сетей Петри строго включает класс свободньсх языков ординарных сетей Петри. Р, С, сс Емс. 42. Д о к а з е т е л ь с т в о. Поскольку класс ординарных сетей является, по определению, подклассом класса сетей Петри, достаточно показать, что существует сеть с кратными дугами, которая порождает свободный язык, не порождаемый никакой ординарной сетью.

Такая сеть показана на рис.4.2. Она порождает свободный префиксный язык ь(д() =( с,. с,с,, с,с,сз), а дпя терммнальной разметки Мг " (О, О] она порождает терминальный язык 1(Д( Му) (ссс,сз). Нмкакая ординарная сеть Петри не может порождать такие свободные языки. Предположим противное. Тогда сеть )Ч = (Р, Т, Р, Ме ), порождающая эти языки, должна иметь ровно два перехода — сс и сз. 1) ПРедположим, чтО Сз ~ ф или ЧР Е Сз . Ме (Р) > О. ПосколькУ Сеть Су — ординарная, то в префиксном языке (.

(д() (. (дс ) должно содержаться слово, мачинающееся символом перехода Сз. но это не так, 2) Предположим, что Вр Е сз. Мч (р! О. Обозначим через Рч Оз) множество всех входных мест перехода сз, имеощих нулевую разметку. Здесь возможны два подслучая. 2.1) Существует место.р такое, что р Е Ре О) Л р Р с;. В этом случае нулевую разметку места р не может изменить ни переход Сы ни переход сз, поэтому сз оказывается мертвым переходом, что противоречит вхождению слова с, с~ ст В язык с. (дс ) 4 Оч! . 22! Ра (сз ) ~ 'С ы т.е.

любое входное место пеРаходл Сз с нУпеаой Разметкой является одновременно выходным местом перехода ты В этом случае язык (. ОЧ') должен содаржать слово с1 сз, поскольку он содаржит слово сы а срабатывание сс увеличивает ма единицу разметку всех мест из Рч (ст), после чего переход Ст может сработать (тзк как сеть ДС' — ординарная) . Перечисленные случаи исчерпывают все возможные варианты сетевых связей между переходами С с и сз, но ни один из мих не приемлем для порождения свободного языка (.

Оч ) = 1(дс!. поэтому не существует ординарной сети Петри, порождающей такой язык. Сз 5 4.2. Автомяпцге свпс и аняхроиюацловвме г(азам Два наиболее простых подкласса сетей Петри образуются за счет наложе. ния строгих топологичаских ограничений на структуру сети, т.е. ограничений на отношения инцмдентности Р, связывающее места и переходы сети. 5$ Сеть Петри с мншкеством переходов Т называется автоматной, асли у С Е ЕТ;)'с)=)с )=1, тл. если каждый переход сети имеет ровно одно входное и ровно одно выходное место.

Пример автоматной сети показан не рис.4.3. Сеть Петри с множеством мест Р называется синхроиизаиионным граФом (или сонхрограФом, или маркированным' граФоы), если )'р) )р ) 1, т.е. если в каждое место сети входит ровно одна дуга и из каждого места исходит ровно одна дуга. Пример синхрографа показан на рис.

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

Поэтому, если переход с сработал при разметке М и изменил ее на разметку М, то М (р) М (р) для асах мест р, не совпадающих ср1 ирз ° М (Р1) + М (Рт ) М(Р1 ) — 1 + М(рт ) + 1 М(Р~ ) + М(рт ). Таким образом, Х М (р) Х М(р), и число фишек в автомат- рир рпр ной сети остается постоянным при ее работе, т.е. автоматная сеть консервативна и ограничена. Отсюда следует также, что автоматная сеть безопасна тогда и только тогда, когда ее начальная разметка содержит ровно одну Фишку. Автоматная сеть живе тогда и только тогда, когда она представляет собой сильно связный граф, т.е.

из любой вершины сети существует путь вдоль дуг в любую вершину, и ее начальная разметка содержит хотя бы одну Фишку. Так как автоматная сеть ограничена, то ее граф раэметок конечен, и, следовательно, в классе автоматных сетей разрешимы проблемы достижимости разметки. проблемы живости, проблемы Я-включения и Я.эквивалентности, проблема эквивалентности по языкам и все другие проблемы анализа свойств сетей. Все это следствие того, что автоматные сети представляют Рис. 4.4. собой, по существуз сетевую форму задания конечных автоматов.

Это непосредственно следует из конечности графа разметок любой автомат. мой сети. Этот граф представляет собой не что иное, как граф конечного автомата, в котором множество состояний образовано множеством достижимых в сети разметок, а алфавит — символами переходов сети. Поэтому на автоматные сети распространяются все результаты теории ко. нечных автоматов, и изучать этот класс в рамках теории сетей Петри не имеет смысла. В ряде случаев при определении автоматной сети накладывается дополнительное ограничение, чтобы ее начальмая разметка имела ровно одну фишку.

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

условие является входным (или выходным) для нескольких переходов- событий. В отличие от автоматнь!х сетей синхрографы могут описывать параллелизм событий,нонедопускаютизображенияконфликтныхситуаций. Основ. ные свойства сетей, и в том числе живость и достижимость разметки, рас. поэнаваемы в классе маркированных графов, причем на основе простого анализа структуры графа м его начальной разметки. Структурные компоненты, в терминах которых формулируются условия огранмчзиности, живости и пр., — зто простой путь и цикл в сети. Простой путь в сети (Р, Т, Р) представляет собой последовательность (х,, кз,..., к„) элементов сети такую, что кзркт+! для 1 <! <и — 1 ик, Фк) ллялюбыхдвухзлемемтов сети, кроме, быть может, ! = 1 и/ = п.

Простой путь называется (простым) циклом, если к, " кгт В счнхрографе на рис. 4.4.а простыми циклами являются пути (т!. Рз гз Р! т!) ° (гз.рз. гз. Ра ° тз) ° из. Рз ° тч. Рз гз) ° Будем говорить, что простой путь(в том числе цикл) содержит и фишек при разметке М, если п — сумма фиозек в проекции М (Ф) разметки М на множество мест Р' ь.р, входящих в этот путь. Т е о р е м а 4.4.

При функционировании синкрографе число (бишен, содержащихся е любом его цикле, остается постоянным. Доказательство. Пусть (к,, хз,..., к„) — цикл (к, к„) в синхрографе )у и пусть, для определенности, к, к„— переход т. Тогда этот цикл можно записать как последовательность (г,, р„гз,..., Рж, т ! ) . Если о М(р,) — число фишек в местахр,,...,Р,„цикла при некоторой т= ! разметке М Е Я()у), то прн смене разметки М на М такую. что М(г ). М . возможны два случая: т принадлежит этому циклу или с не принадлежит ему. В первом случае разметка мест р,,..., Рж не изменяется при смене М на М, так как эти места инцидентны только переходами цикла и ме могут получить или потерять фишки при срабатывании переходов, не входящих в цикл. Во втором случае срабатывание любого из переходов цикла приведет к перемещению ровно одной фишки из его входного в его выходное место.

Оба эти места принадлежат циклу.и поэтому Х М (р!) (= ! М(р,). С) ! На рис. 4,4,в цикл В„р,, гэ, р,, т, ) ссдерлшт две фишки лрм любой достижимой разметке, цикл (г», р», Г», рч, т») — ни одной фишки, цикл (т», р,, гь, рь, г»] — одну фишку. Простой муть (в том числе цикл) будем называть пустым (нвпустым) при разметке М, если он нй содержит ми одной фишки (если он содержит хотя бы одну фишку) прм атой разметке. Цикл М».

р», г», рь, г» ! — пустой в синхрографе на рис. 4.4,в. Т е о р е м а 4.5. Переход г — потенциально хшвой в синхроарэфе, вели и только если он нв входит яи в один пустой при Ме цикл и ни в один пустой при Ме путь из пустого никла. д о к а з а т е л ьст во. В силу теоремы 4.4, если переход т принадлежит пУстомУ пРи Ме циклУ, то он никогда не сРаботает, так как его входное место, входящее в пустой цикл, никогда нв получит фишки. Путь иэ цикла в синхрографе может начинаться тое ко переходом.