Книжка по сетям Петри (547616), страница 9
Текст из файла (страница 9)
П Т е о р е м а 2.14. Проблема эгиеасги сети Петри и проблема дссгижимости в нвй праиэволыюй разметки эквивалентны. Доказательства Прямовследствиетеорем 2.12и2,!З,С» ГЛАВА 3 языки скткй пжтги Проблемы, рассмотренные в предыдущей глава. связаны в большей степени с разметкой сети и соответствуют таким прикладным задачам, которые требуют анализа возможных ситуаций )состояний) в моделируемых сетями системах, анализа характера изменаний условий в них. Другой круг проблемы связан с анализом динамики функционирования системы, с характероье множеств возможных последовательностей реализации событий. Поскольку события системы представлены переходами сети, ее функционирование можно описать в терминах последовательностей срабатываний переходов.
Множество /. 1)У) последовательностей срабаты. ваний сети ПетриВ представляет собой подмнахество множества Т'всех слов, составленных из символов переходов сети, т.е. всех слов в алфавите Т. Таким образом, множество Е ()У) является языкоы в алфавите Т. Этот язык называют свободным языком сети Петри. Множество свободных языков всех сетей Петри образует класс свободных языков Х' сетей Петри. В сети все символы-переходы различны.
Однако в системах, моделируемых сетями, чжто удобно считать разные события одинаковыми, тождественными в некотором смысла. Например, разные операторы программы могут текстуально совпадать, или, другими словами, представлять собой разные вхождения в программу одного и того же оператора. В конвейер. ной линии могут быть встроены в разных местах одинаковые устройства. В сетях Петри, как они определены в %1.2, нет средств для изображения таких ситуаций. Однако это можно легко испрэвитгь введя специальные пометки, отмечающие "одинаковые" и "разные" переходы.
Эти пометки представляют собой символы из некоторого алфавита, в общем случае отличного от алфавита Т, а сами сети называет помеченными. Если символы переходов в последовательностях срабатываний заменить на помечающие символы, то свободный язык сети преобразуется в некоторый другой язык, порождаемый этой жа сетью. В зависимости от правил пометки переходов и от правил формирования последовательностей срабатываний выделяются различные классы языков, порождаемых сетями Петри. Эти классы сравниваются в данной главе друг с другом и с языками, порождаемыми другими типами абстрактных систем, предназначенных для моделирования дискретных систем, в частности, с языками конечных автоматов и машин Тьюринга.
Такое сравнение позволяет характеризовать моделирующие возможности сетей Петри, их способность адекватно описывать системы со сложной динамикой функциониро. вания. Оказывается, что моделирующие возможности сетей Петри вьние, чем у конечных автоматов, но ниже, чем у "универсальных" систем типа машин Тьюринга. В этой главе рассмотрены также массовые алгоритмические проблемы для различных классов языкэв сетей Петри. 3 3.1.
Помеченные сети и классы языков сетей Петри Помеченная сеть l)егри — зта пара ()У, Е), где(У- сеть Петри, Е:Т А- ломечаюиаая функция над некоторым алфавитом А. Если Е- частичная функция, т.е. некоторым переходам не сопоставляется никакого символа из 4, то зти непомеченные пе)мховы назьаваот Л.переходами и помечают одним и тем же "пустым" символом Л. Помечающая функция Ервсщиряется на последовательности срабатываний естественным образом: ~ Е (т) Е (г), если Е (о ) определено, Е (гг) ~ Е (т') в противном случае. где ггЕ Т'.
При етом Е (Л) Л, где Л вЂ” пустоеслово. Помеченные сети с Л переходами удобны в тех случаях, когда при моделировании системы нужно ввести вспомогательные переходы, не связанные непосредственно с событиями системы, а используемые для некоторых специальных целей моделирования. С их помощью можно также "маскировать" те события, которые не должны рассматриваться в данной задаче моделирования.
На рис, ЗП, е показам пример сети Петри, на рис. 3.1, б, е и г — помеченные сети над алфавитом(а, Ь,с, д), полученные из первой сети с помощью следующих помечающих'функций: Еа ° а Иа ) а, Еа (га! с, Еа (гз) Ь, Ег (гс! д, Еа: Еа (га! а. Еа (га! ж Еа (га) Ь. Ег (гс) -Ь, Еа ° а (г, ) =Л, Еа (га) =а, Еа (га)=Ь, Еа (гс) =с. Если т Е Т* — последовательность срабатываний сети Петри )У, а (ДГ, Е)— помеченная сеть, то Е (Г) Е Я ' называют псмечмоиягй последовательностью. Если Ь ()У! - свободный язык сети В, то множество(Е (г) ! г Е Ь (ДГ)) абразует лрефикскый язык помеченной сети Я, Е). Во многих приложениях бывает удобно или необходимо рассматривать не свободный язык сети Петри Д( включающий все ее последовательностм срабатываний, а его подмножество термияаяыгых последовательностей, которое состоит из всех последовательностей, ведущих от началыюй разметки Мс к некоторой фиксированной терминальной разметке М, т.е.
множество Ь ()У, МТ! "(г Е Т' (Ме (т ) М ) . Чможество Ь ((У, Мг) образует сесбодныи терминальный язык сети )У. Соответственно мможество(Е (г) ! т Е Ь (й(, М )) образует терминальный язык поьаеченной сети (Д( Е1. Рнв 3.1. Для сети Ина рис. 3.1, а свободный язык представляет собой мнакество Х Оу) ((7 Ф гэ' г," ~ (и, >0)л ~1 >па Э 0) л (пу ' пт ~ пз ~ 0)л(пт )п4 ~ 0)) а свободный терминальный язык Х (И, Мг), где Мг (О, О, О, 1) (т.е. при Мг только несторе содержит фишку), представляет собой множество Х (И, МТ) =((Т гэ гэ гч ) л>0 ).
Поскольку для помеченной сети на рис. 3.1, б помечающая функция Е~ осуществляет взаимно однозначное отображение множества Тна алфа- вит А, то ае префиксный язык и терминальный языки получается из выше- приведенных языков прямой заменой символов.параходов на соответству- ющие символы из А. Для помечанных сетей на рис. 3.1, е и г их префикс- ные и терминальные языки (для МТ (О, О, О, 1)) образуют множества: Х (И, Тэ) =(а" Ь'" (п>гл 0), Х (И, ьэ, Мг) (а" Ь (п>О), (. (И, Еэ) ( е"' йч' сгч ( (1 Э и, ~ 0)л(п~ = 0 мпа 0)л (л~ = 1 пэ >0)л(п, >пэ >О ) ), Х (И,Е,Мг) (аЬ"с)п>О>.
Пусть г'- класс всех сетей Петри. На основе введенных выше определе- ний языков разного типа для сетей Петри и помеченных сетей можно обре- зовать различные классы языков сетей Петри, иэ которых выделим следу. илцие. 1) Класс Х~ префиксных языков сетей Петри включает прафиксные язы- ки всех помеченных сетей, которые можно образовать из сетей класса Ф'с. помощью произвольных помечающих функций над произвольными алфави. тами. Верхний индекс л указывает, что помечающие функции могут быть частичными, т.е. помеченные сети могут содержать Х.переходы. 2) Класс Х» терминальных языков сетей Петри включает терминальные языки всех помеченных сетей, образованных из сетей класса г', в том чис- ле помеченных сетей с Х переходами.
3) Классы Х и Хе являются подклассами классов Х и соответственно Х~е и включают префиксные и тдхиинальные языки всех тех помеченных сетей, которью не содержат )ьпереходов, т.е. которые образованы из сетей класса.Ф'только Е помощью всюду определенных помечающих функций. 4) Классы Х~, Хь включают свободнью префиксные языки и свободные терминальные языки всех сетей Петри, Если условиться, что существует специальный класс асхщу определенных помачаехцих функций типа г.': Т.
-+ Т,т.е. функций нздалфавитом 4 = Т. причем'ч (Е Т: з (П г, то классы ЮГ и Хьг можно считать подклассами классов Х и соответственно Х„. Для сопоставления друг с другам введенных выше языков и классов сетей Петри полезной оказывается специальная стандартная форма поме- ченных сутей. Сетгч преобразованная в стандартную форму, сохраняет префиксный и терминальный языки, хотя в стандартной форме и появля- ются новые переходы и места.
Помеченная сеть представлена в стандартной форме, если: 1) выделено специальное "включаххцее" место оп с начальной размет- кой Ме (оп) = 1 и начальная разметка всех остальных мест равна 0; 2) терминальный язык сети всегда определяется дпя одной и той жа теРминальной Разметки Мг О = (О,..., О), где и )Р) — число мест в сети; 37 3) каждый переход сети имеет хотя бы одно входное место (т.е. размет. ка О является тупиковой для сети) . Л е м м а 3.1. Для любой помеченной сети ()у, Я и любой терминальной разметки Музгой сети существует лрвдстввявякая е стандартной (бщтмв яомвчеянвясеть (д(', Е') такая, что(. (Ю', Х'] = (.
(д(,Х) и (. ()у', Х', О) = А ()У, Е, М ]. Доказательство. Пусть)У = (Р, Т,Е, УУ,Мс). Если зта сеть содержит переходы без входных или выходных мест, т.е. не удовлетворяет третьему условию стандартности формы, то в сеть добавляется новое "стандарт. ное" местов, которое делается входным и одновременно выходным для каждого перехода сати (такиа места уже вводились выще, при доказательстае теорем параграфов 2,3 и 2.4). Начальная разметка Мс распространяется на новую сеть так, что Ме (о) = 1. Введение места о не изменяет ни условий срабатывания переходов исходной сети, ни разметку ее мест после срабатывания переходов, поэтому новая сеть сохраняет свободный, префиксный и терминальный языки заданной сети (последний с учетам добавления к Му компоненты Му (о) 1) .
На рис.3.2, а и б показан пример описанного преобразования помеченной сати, содержащей переходы с пустым множеством входных или выходных мест, в сеть удовлетворяющую третьему уело. вию стандартности. Для того чтобы выполнилось первое условие стандартности, добавим к сети вкюсчающее место оп с единичной разметкой, разметку всех осталь. ных мест сделаем нулевой, а дпя каждого перехода т е Т, могущего сработать при начальной разметке Мс, введем новый переход т с пометкой Е (т ) Е (г). Каждый из новых переходов имеет в качестве единственного масте включающее место оп, а его выходные дуги заводятся на места сети так, чтобы после срабатывания перехода г разметка этих ыест равнялась бы разметке преобразуемой схемы после срабатывания перехода (при Ме, а именно: Е' (Г') Ме — Е' (т]+ Е' (Г).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
