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

Легко видеть, что любое слово Е (т) Е й (У, Х), т Е (. ((У), принадлежит также языку новой сети и порождается ее последовательностью т, отличающейся ст т лищь первым символом перехода (г в г вместо т в т ) . Наобо. рот, любая последовательность срабатываний г новой сети должна начинаться некоторым символом перехода г, так как ни один нэ "старых" парехо. Рис. 3.2. дов сети не может сработать из.за тато, что асе маета..кроме места оп, имеют нулевую разметку.

Продолжение посладовательности срабатываний т' должно далее совпадать с продолжанием некоторой последовательности срабатыванийтстарой сети, начинающейся символом перехода с. На рис3.2, 6 ив показан пример описанного преобразования. В исходной сети на рис. 3.2, б при разметке Ме могут сработать переходы с, и сэ, для которьж введены Аапапннтапьнью $юрахады с1 н сэв 'НОВОЙ сети на рнс.

3,2, в. Срабатывание парахада с1 меняет разметку Ме на разметку (2, 1, 1), где переход д считается третьим в упорядоченном наборе мест, а срабатывание перехода сэ меняет разметку Ме на разметку [О, О, 1). П~ютаму в новой сети.г (С,') (2,1,1)иг'(Сэ)=(0,0,1). Чтобы выполнить второе требование стандартности формы, для каждо. го перехода сЕ Тткого, что он последним макет сработать перед терминальной разметкой МС(т.в. МГЭ г' (с)), добавляетея новый пераходС' с пометкой Х (с") = Е (П. Входные дуги, ведущие в переход с", завалятся так, чтобы 'Е (сн) =М- Р'(с)+ Р(с], а выходных дуг переход с не имеет (т.е. г' (с ) О).

Из построения следует, что сн может сработать в новой сети только в том случае, если с можвтцюботзть (так как 'г (с ) >'Е (сИ, и что срабатывание с приводит к нулевой разметке 0 в том н только том случае, зепи срабатывание с в еетийпривалнт к разметке МП Соответственно последовательности срабатываний т и т' такие, что М, [т) Мр Ме[т'>О длина[т(=(т( 2, отличаются лищь последними символами переходов (С вт вместогвЕ).В случае,если)т[ [т') 1, т.е.Мь [С)М, Дпя С добавляется еща переход с"' с Е (сн'> = Х [П. Его единственным входным местом служит место оп н г (с ) = О. Не рис.

3.2, е и э показан пример описанного преобразования для тер. минальной разметки М~ (3, О. 1), где д — третий элемент набора мест. Эта разметка достижима в сати на рнс. 3.2, б после последовательностей срабатываний, заканчивеащихся символами переходов с, ипи сэ. В первом случае имеет место изменение разметки (2,0, 1) [с, >(3 О, 1), во втором (4, 1, 1) [сэ >(3, О, 1). В сетьдобавпяются переходы с, и сз с р(с",>=(3.0.1> — (1.0.1)+(0.0.1)-(2.0, Н.

'г (Сэ) (3.О. 1) — (О. 0 1)+(1.1. 1) (4.1 1). Е (с", ) = а, Х (с",) с. П С лед с т вне. Любод яэык иэ кпеееоеС, С",Сь, Сьо макет быть порожден ненотород поыечанноб еегью е стандартной С(кухне как ее нрнинапьныд язык длн терминальной разметки М. О. Это позволяет переносить любые результаты о языках сетей, представленных в стандартной ферме, на общий случаи языков сетей Петри. Следующие теоремы сравнивают введенные выше классы языков сетей Петри. Теорема 31. а) СССь,б) СССе.

Доказательства Сначала установим, чтоСйСь и С~ь„Сы а за. там убедимся, что зги включения ляпяются на свмом депе строгими. Покажем, что дпя любой помеченной сети (И, Е) можно построить помеченную сеть (И, Е ! такую, что Ь ОУ„Х) Ь (И', Е ) Ь ЙУ, Е, 0), а ь а (а'г) т.е. префиксный и терминальный (для д д >) г; г Мг 6) языки сети [И', Е'! равны 6 друг другу и равны префиксному язы- ку сети (И, Е) . При етом, если сеть (И, Ф Е> не имеет Л-переходов. то сеть (И, ([ Х)также не должнаиметьЛпереходов. б Заменим каждый переход г б Т Рчс.

3.3. множеством переходов (гг[ Р(г))= Р(г)ЛР(г))~Р (г)!. Здесь индекс г' меняется от 0 до х, где lг равно числу различных векторов длины (Р(, меньших или равных Р' 01, и пусть при) = О новый переход ге является точной копией перехода г, т.е. Р' (Ге) = Р' (г!. Кроме того, полагаем, что для всех г) Е (г') = Е (г), т.е. все новые переходы помечаются так же, квк и заменяемый ими старый переход.

На рис. 3.3, б показана помеченная сеть, построенная описываемым способом по помеченной сети на рис. З.З,а. Каждый из новых переходов г' может сработать точно при той же разметке, что и замещенный старый переход. Но после срабатывания он может выдать меньше фишек, так из него выходит меньше дуг (при )' чь О), чем из г. рассмотрим произвольную последовательность срабатываний г сети (И', Х ), приводящую к некоторой разметке М, т.е.

Ме [г )М. Если заменить в т' каждый переход г) на г, то получим последовательность срабатыванийг сети (И, Х), причем Ме (г>МЛ М>М'. Наоборот, если задана последовательность срабатываний т б Ь (И, Е'» такая, что Ме [т ) М, то можно последовательно заменить в ней каждый переход г на г) так, чтобы на каждом очередном шаге замены выбирался г) с наименьшим вектором Е' (Г)), позволяющим, однако„спхранить остамиуюся часть последовательности. В результате последнее срабатывание "новой" последовательности г' должно привести к нулевой разметке в сети (И', Е') .

В обоих случаях последовательности срабатываний г и г' порождают одно и то же слово Е (с! = Е (т ). Например.если выбрать г = г[ ге~ гзз такую. что (2, О. 0) [г > (О, 0; 0), в сети марис. З.З,б, тодля неесуществуетгЕ(. (И, Е), где (И, Е)- сеть на рис.3.3, а, причем г = г, г, гз, (2, О, О) [г) (О, О, 1), Х (т) = а а Ь = Е (т'1. Наоборот, длит =т,.г, гз г,, гдетЕ1. (И, Е) и (И, Е) — сеть на рис. 3.3, а и (2,0,0) [т>(0,0, 1),существуетт'б(. (И',Е'),где(И' Е'! — сеть на рис. 3.3; б нг =г, г>г>гз,причем (2.0.0) [г'> (0,0,1),аХ (т)=аеЬа Е(г).

Таким образом, из спософа построения сети (И', Е') следует, чтоб (И. Е) = = Ь (И, Е ) - Ь (И, Х, 0). Например. для сети (И, Е! нв Рис. 3 З,а ппефиксный язык Ь (И, Е! =(а,аа, ааЬ,вала,ааЬеа). Для сети .(И', Е') на рис. 3.3, б префиксный язык Ь (И', Х') Ь (И', Е', 011 (а,аа,ааЬ, авЬа, ааЬае)=Ь ОУ, Е!. Следствием установленного соотношения между префиксным языком сети (И, Е) и префиксным и терминальным языками сети ОУ', Е') является включение Х Я Хо.

Ю Чтобы установить справедливость соотношения б), достаточно убедить- ся, что в жсбую помеченную сеть Патри можно власти дополнительныа й-переходы таким образом, чтобы купава~ разметка была достижима от любой разметки сати и прафиксные языки новой и старой сети совпадали. Длл этого достаточно для каждого эааста заданной сати ввести свой й пере- ход без выходных дуг, который иэй(кает при своам срабатывании по одной фишке из этого места. Новые Х.переходы могут срабатывать в любое жэа- мя, уменьшая разметку сети.

Для любой последовательности срабатываний г исходной сети найдется такая последовательность срабатываний г новой сети, что 1,' (т) =,ь (г'). Обратное также верно, поэтому префиксные языки обеих сетей совпадают. Отснэ(а следует, чтоХ" ь„.Хм Тммрь убедимся, что установленные включения являются строгими.

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

Для доказательства справедливости строгих включений в этой и в следующей теоремах будет использован один и тот же прием, а именно: будут предъявлены языки, принадлежащие правым классам языков и не входящие в левые классы языков. а) Легко построить помеченную сеть в стандартной форме, псролщжо- щую терминальный язык (. ~ =(г, г г г) (см. доказательство теоремы 3.1), но никакая сеть Петри не монет породить такой же свободный терминаль- ный язык.

Действительно:, пусть переход С вЂ” единстванный потанциально живой переход в некоторой сети Петри И. Он может сработать при нечаль- ной разметкеМе, т.е. Ме >'Р В). Разметка й( возникмощая после сраба- тывания перехода г, может удовлетворять или не удовлетворять условию М > "Р В). В первом случае язык Е (И) будет также содержать все слова вида (" (в силу теоремы 1.1) . Во втором случае слово т оказывается един- ственной последоветельностыо срабатываний, т.е. слово г г т не входит в язык Е,. Таким образом, Е1 ЕХо иЕ, МХТе, те ХХСХе. б) Легко построить помеченную сеть, пс(кэкдаощую п(юфиксный язык Ет (е, аа, эеЬ, Ь, Ьэ, Ьаа ), но никакая сеть Петри не может породить Ез в качестве свободного языка.