Книжка по сетям Петри (547616), страница 19
Текст из файла (страница 19)
гг»гибиторлая сеть представляет собой сеть Патри, дополненную специальной функцией инцмдентности Рт. Р Х Т. (О, 1), которал вводит иигибиторкыа дуги длл тех пар (р, с), для которых Рс(р, с) 1. Ингмбиторнью дуги связывают только места с пераходамм, не рисунках мх изображают заканчивающимися не стрелками, а маленькими кружочкам)ь Правило срабатыванил переходов в,ингибиторной сати модифицмруется следующмм образом. Переход с может сработать при разматке М, если ур Е 'с: М(р) > р(р,с) л М(р) ° Рт(р,с) О. Другими словами, лареход с может сработать, если каждое его входное место р. соединенное с С "обычной" дугой с кратностью )У(р, с), содержит не менее Иг(р, с) фищек, а каждое входное масте, соединенное с с ингибиторной дугой (ее кратность всегда равна 1), имеет нулевую разметку. Исгюльзуя ингибиторную дугу, можно промоделировать оператор услов.
нато вычитания еюм хс чь О то х~, хт — 1 фрагментом ингмбиторной сети, показанной на рис 64, а. Место хс соответствует счетчику хт, срабатывание пеРехода С' — альтеРнетива, слатанной с выполнением Условна хг та О и последующим вычитанмем единицы из хп срабатывание переходе с" альтернативе, связанной с выполнением условия хг ~ О. Длл построения ингибиторной сети, моделирующей счетчиковый авто. мат, достаточно каждому оператору программы автомата сопоставить моделирующий его фрагмент ингибиторной сети н зетам связать эти фрагменты в алиную сеть, С этой целью символы входных н выходных "управляющих" мест переходов в фрагментах сати выбираются в соответствии с метками операторов в автомате, как показано на рис.
6.4, а каждому счетчику х, автомата сопоставляется место х,. Переходы, соответствующие опараторам печати, помечаются соответствующими символами, остальные переходы вводятся как Х.переходы. Фрагменты связываются в сеть путем слияния одмнакоео яомечемных выходных и входных мает. Т е о р е м а 6,2. Любод рекурсивио леречислимыд нзы» «ахют быть лороадеи помечен»од иигибитор»од сетью ка» »раб)икс»ыд или прыи»альныд лэык сати. Д о к а з а т е л ь с т в о.
Способ, которсим строится помаченная ингибиторная сеть, моделирующая счетчикоаый автомат, непосредственно убеждает в эквивалентности терминальных языков, порождаемых обеими систамэми, еслм длл сети фиксироветь терминальный нзык с такой резматкой Мр при которой вса маета сети, кроме места, соответствующего оператору стоп, имеют нулевую разметку, а это место — единмчную. Таким образом, класс Х~~(С) всех терминальных языков (помеченных) ингнбитоьрных сетей является классом ракурсивно перечислимых языков.
Класс б (Д образован префиксами языков из класса Юе (() рекурсивно перечислимых языков и поэтому он также является классом рекурсивно пере. числимых языков. П При описании функционирования сетей Петри (глава Т) отмечаюя надатерминизм следующего рода: асли ~ асколько переходов могут сработать, то срабатывает любой из нмх. В реальных дискретных системах имеют место ситуации, когда из двух готовых работать устройств требуется запустить сначала одно, например, первое.
а ватам второе. Другими словами, одно из устройств имеет приоритет не запуск перед другим в том случай, если обг готовы работать. Эти ситуации не ьтоделируются Тг в сетях Патри в силу принятого в них преамла срабатывания нвсколысих готовых к срабатыванию переходов. Модифицируем опрадвленнв сети Петри следующим обрезом. Введем множаство приоритетов РЯ, элементы которогр частично упорядочены некоторым отнощвнием С (меныив или равно), С каждым переходом с сети Петри свяжем вго приоритет рг(с)' Е Рг). Правило срабатывенип перехода модифицируем, дополнив его условием: переход с может сработать, вопи дпя любого другого перехода с этой сетм, который может сработать по стандартному условию, рг(с') ( рг(с).
Другими словами, вопи несколько лереходое готовы сработать, то срабатывает любой такой переход, приоритет которого на меньщв приормтетов остальных готовых к срабатыванию переходов. Таку)о модмфмкацию сети Петри называют сетью с приоритвтаыи. Сд! Р б) Рис. 6.6. На рнс. Е.б,.а показан пример простой сати с приоритетамн, дпя которой а качестве множества приоритетов выбрано множество натуральных чисел и отиощение совпадает с отнощением "болыие или равно". Пусть ргфз) а 1 < рг (с~) е 2.
Если Мч (э~ ) О, то ни один нз переходов не может сработать. Если Мв (рз ) 1 м' Ме (рз) О, то срабатывает только переход сз, который мремещает фмюку из места рз в место р». Если М» (р,) *М» (рз) 1, как показано нарна.б.б,е,то нестандартным уело. виям оба переходе могут сработать, но поскольку рг (сз) < рг (сз), то в этой сети с приоритетами разрещвно сработать только переходу сз, котарый лзшюет оба своих ехоеных места фнщак н помещает фищку на место рз. Лагко заметить, сравнив денную сеть с ингибиторной сетью на рмс. 6.4,в, что обе они функционируют одинаково и что поэтому сеть на рис.6.6, а моделирует оператор условного вычитания вдмнмцы счетчико.
арго автомата. Отсюда следует справедливость следующей теоремы, аналогичной теореме 6.2 как ло формулировке, так и по доказательству. Т в о р в м а бтй Любод ренурсиено ппэечиснимыд Йын может быть порохсдвн помвчвннсд свтыс с лриаритетаыи накав лрзб)инсныд ини пбхииз нвньныд нзын. Т в о р е м а 6.4. С)робнемы оараниченносш, доситимосш, знаиеаненг. ности по прв(бинсныы и терееинаньным языкам, пустоты этих нзыное нераарвзиимы Влн инзибиторных сеид и сетад с приоритетами.
До и а з а т ел ь с т в о. Для мащннэзинского и, следовательно,счет. чиковых автоматов неразрещима проблема остановки (Ьстанаеливаетсп лн мащмна, начав работать с заданными начальными значениями счет'чикоа1) . При построении ингибмтормой сети, моделирующей заданный счетчмкоаый автомат, счетчику кс е сети соответствует место хс, а текущему состолнмю счетчика кс — твкУщеп Разметка места хс. ПОзтомУ(пРоблемв огйани- ченности места в ингибиторной сети равносильна проблеме ограниченности счетчике в автомате. Последняя проблема неразрешима.
Чтобы убедиться в этом, достаточно показать неразрешимость "более узкой" проблемы, а именно — не существует алгоритма, который для любого счетчике может установить, будет ли его начальное нулевое значение изменено хотя бы один раэ, т.е. является ли счетчик Оччграниченным или нет. Преобразуем произвое ный заданный счетчиковый автомат следующим образом. Введем дополнительный вспомогательный счетчик к, запись в который делается только после того, как исходный автомат останавливается, выполнив заключительный оператор стол. Для этого достаточно заменить этот оператор на последовательность операторов к: "к + 1 и стоп.
Если бы была разрешима проблема Оюграниченности, то мы могли бы решать проблему остановки счетчикового автомата. восгюльзовавшись описанным преобразованием. Таким обрезом, проблема 0 ограниченность не может быть разрешимой и, следовательно, неразрешима более общая проблема ограниченности счатчиков и проблема ограниченности ингибиторной сети. Аналогично доказывается неразрешимость проблемы ограниченности в классе сетей с приоритетами и проблемы достижнмости в обоих классах обобщенных сетей. Неразрешимость проблем эквивалентности и пустоты языков следует из теоремы 5.3 и неразрешимости этих проблем дпя рекусивно леречиспимых языков. (:( Т е о р в м а 5.5.
Классы ингобигорнык сегеди сеид с приормгетвми строго мощнее класса сегед Петри и раеноыощны классам машин Тьюринга и Минского, г.е, являются "универсально ыощныыи". Д о к а з е т е л ь с т в о. Непосредственно следует из теорем 3.6, 5.2 и 5.3. В частности, контекстносвободный язык, относительно которого установлено в доказательстве теоремы 3.6, что он не порождается никакой из помеченных сетей Петри, порождается в качестве терминального (в том числе свободного) языка ингибиторной сети, показанной на рис.5.5,6. П 5 5.3. Раскрашенные, синхронные н самомодифивируемые сечи Описываемые в этом параграфе модификации сетей Петри предлагались в первую очередь для того, чтобы более адекватно и удобно выражать в терминах сетей особенности функционирования реальных дискретных систем.
Зги модификации приводят к классам сетей, строго более мощным, чем класс сетей Петри. Например, при моделировании сетями Петри дискретных систем фишки часто соответствуют объектам, передаваемым от компонента к компоненту системы (данным в информационных системах, деталям, ресурсам и т.пд. Зачастую эти объекты имеют дополнительные атрибуты, позволяющие различать их н использовать эти различил для управления функцио. нированием системы. Однако фишки в сетях Петри "безлики" и не отражают такие различия.
Пусть необходимо описать с помощью сетей Петри фрагмент операционной системы, управляющей обменами между тремя накопителями на магнитных дисках О,, От, Оз и центральным процессором ЦП через два канала А и д. При этом требуется, чтобы О, использовал канал А, Рз — канал В, Оз — оба канала А и В. Для адекватного описания подобных ситуаций можно использовать модификацию сетей Петри, в которой фишкам приписаны некоторые признаки, например, различные цвета, а условия срабатываний переходов и правила изменения разметки сети задаются специальной таблицей, учитывающей цвета фишек.
Пример такой раскреиюнкод сеги показан на рис. 5.6. 74 Рис, в.э. В этой сети использованы следующие Фишки с признаками: 222, 222, ОЗ вЂ” фишки, ОтмэчаЗОЩИС эозможнОСть СвязИ С ДИСКОводэмИ 77! 772 ° ~73 э, б — фишки, отмечающие доступность каналов Я и В; и, 8, Т, 6, е — вспомогательные фишки для запоминания предыстории Функционирования системы. Для каждого из шести переходов сети имеется индивидуальная таблица условий срабатывания. В ней столбцы, связанные с входными местами перехода, содержат сочетание конкретных признаков фишек, при котсрь2х переход может сработать. Столбцы, связанные с выходными местами перехода, указывают признаки, с которыми переход добавляет фишки в свои выходные места для каждого входного сочетания признаков. Признаки фишек указаны на рисунке рядом с ними.
Эта сеть моделирует упоминавшийся выше фрагмент операционной системы. Выразительная мощность раскрашенных сетей зависит от мощности множестве признаков, Класс сетей с конечным множеством признаков эквивалентен классу сетей Петри [71, 89], хотя при преобразовании раскрашенной сети в сеть Петри могут значительно возрасти размеры сети. Сети с бесконечным множеством признаков могут моделировать счетчиковые автоматы, и, следовательно, класс таких сетей равномощен классам ингибиторных сетей и сетей с приоритетами. Идея моделирования проста и состоит в следующем.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
