Книжка по сетям Петри (547616), страница 13
Текст из файла (страница 13)
П Формулировку проблемы пустоты для языков сетей Петри приходится модифицировать по сравнению с обычной, так как языки сетей Петри всегда содержат хотя бы одно слово, а именно — пустое слово Л. Для префиксных языков из классов Х и Х можно считать, что они не пусты, если содержат хотя бы одно слово, отличное от Л. Терминальный язык Х (Д(, Е, Му) из класса Хе или Хе можно считать пустым тогда и только тогда, когда пуст л свободный терминальный язык Х (И, МХ), последний, в свою очередь, пуст тогда, когда Му р Я(й) .
После уточнения формулировок легко доказываются следующие теоремы. 49 Т е о р е м а 3.10. Пройюма пустоты разрешима для првфиксных язы. ков иэ классов Х и Х ь. Д о к а з а т е л ь с т в о. Для произвольного языка из Ю или Х~, порождаемого помеченной сетью, достаточно проверить, может ли сработать при начальной разметке хотя бы один переход этой сети, помеченный некоторым символом из ломечающего алфавита (символом, отличным от А) . О Т е о р е м а 3.11.
Пройюма достижиыости разметки и проблема пустоты терминальных языков из классов се и 4 эквивалентны. Д о к а з а т е л ь с т в о. Так как для любого терминального языка (. ()У, Х, Му) верно, что он пуст тогда и только тогда, когда Мг 4 Я (Ю, то проверка пг готы языка сводится к проверке достижимости разметки М~ в сети Д( и н оборот. О Т е о р е м а 3.12. Проблема конечности разрвиеыа дпя првфиксных языков иэ классов , и Х ", До к а з а т е л ь с т в о. Пусть задан язык, порождаемый помеченной сетью Щ й ) . Он бесконечен, если и только если содержит бесконечную помечающую последовательность.
Добавим к сети ()У, Х) новое место~четчик р, которое является выходным местом всех помеченных переходов, и р = = (). В процессе функционирования сети после каждого срабатывания помеченного перехода место. счетчик получает фишку. Это место ограничено тогда и только тогда, когда сеть ((У, Х) не порождает ни одной бесконечной помечающей последовательности. Поскольку проблема ограниченности некоторого места в сети Петри разрешима (теорема 2.3), разрешимой является и проблема конечности префиксных языков.
О Т е о р е м а 3.1 3. Проблема достижиыости разметки сводима к пробна Х аю конечности терминальных языков иэ классов Хе и Хе . Д о к а з а т е л ь с т в о. С учетом теоремы 3.11 достаточно показать, что проблема пустоты терминальных языков сводима к проблеме их конечности. Пусть порождающая заданный терминальный язык помеченная сеть представлена в стандартной форме. Добавим к сети помеченный некоторым символом переход и этот переход соединим входной и выходной дугами с включающим местом оп. Новый переход не влияет на достижимость терминальной нулевой разметки. Если для исходной сети существует терминаль.
ная помечающая последовательность (для Му = О), то тогда в модифицированной сети существует сколь угодно длинная терминальная помачающая посладовательность, получаемая за счет того. что сеть начинает рэ1оту с произвольно большого числа срабатываний добавленного перехода. Поэтому терминальный язык модифицированной сети бесконечен в том и только том случае, если язык исходной сети не пуст.
О При решании проблем эквивалентности и включения для языков сетей Петри предполагается, что все помеченные сети определены над одним и тем же алфавитом (полученным, например. объединениам алфавитов, для которых заданы разные гюмечающие функции) . Пробгюмы эквивалентности и включания оказываются неразрешимыми лля классов языков Х, Х, Хе, Хе, причем доказательство неразрешимости этих проблем проводится аналогично доказательству неразрешимости проблем В.эквивалентности и В-включения для сетей Петри, а именно сведением к рассматриваемым проблемам неразрешимой проблемы включения гра. фов полиномов (см.б 23). Напомним, что граф б (О для полинома Пх ы хз,..., х„) с неотрицательными целыми коэффициентами представляет собой множество ( (х,,..., х„, у) к (ч " г ( у < ~(х,,..., хх ) ) .
50 Для сведения проблемы включения графов полиномов к проблеме включения устраивается кодировка графюв языками над помечающим алфавитом. При этой кодировке каждому вектору, принадлежащему данному графу полинома, взаимно однозначно сопоставляетсл слово кодирующего языка. Кодировка опирается на предположенный Париком (67] метод отобракения слов в заданном алфавите А (а,,..., а„) в Рчс. 3.9. целочисленные векторы. Отображение Парике для алфавита А представляет собой функцию Ф А*-'й)ч такую, что длл а ЕА' вектор йа содержит в качестве ~'-го компонента целое неотрицательное число, равное числу вхождений символа а; Е А волово а. Например,для алфавита А=(аыаз,аз) ислаева ага,а,вз векторба= =(2, 2, 0). Отображение Парика распространяется на языки над алфавитом А естественным образом: ФС '" (М Е й)" ) Ва Е (.: М (]а ) .
Л е м м а 3.2. Для любого полинома т (х,,..., х„) с неотрииательными целыми коэффициентами ьюжно построить помеченную сеть (й Х) без й-переходов такую, что префиксныд язык (. (И, Х] «одируег граф р (т) полинома с помощью отображения Парика для алфавита А =( а,,...,а„, а„+1 ) следующим образом: (. (й, Х ) является максимальным языком, для которого (т(. (И, Х] =р(г). Доказательство.
Пусть й' — сеть Петри, слабо вычисляющая полинам т (х,,..., х„) (см. з 2.3) . Строится помеченная сеть (й, Х ) способом, указанным на рис.ЗЭ. Добавляются новые переходы г~,...,г„ по одному для каждого входного месте м,, ..., )п„сати й, стартовое место ! оп сети И. делается входным и выходным местом каждого из добавленных переходов, переход ты 1 Ю ~п, соединяется выходной дугой с местом (пы соответствующим переменной х~ в полиноме. Помечающая функция Х выбирается таким образом, что Х(г] а„ь, для любого старого перехода г сети й и Х(г!] = ат для каждого нового перехода т!, 1 чу <и, сети И.
Следовательно, сеть (.И, Х) не содержит )( переходов. Начальная разметка Ме сети (И, Х) такова,чтоМе (оп) = 1 иМе Пп1) "О для всех ) от 1 до и. В сети (И, Х) ни один из старых переходов, помеченных символом в„+ ы не может сработать, пока один из ник не удалит (насовсем) фишку из места оп. Это означает, что все срабатывания новых переходов в сети (й, Х] предшествуют срабатываниям старых переходов, общих для сетей й и й. Поэтому префиксный язык (. (й, Х) удовлетворяет следующим свойствам: 1) (.(И, Х) ь (а,,...,а„)' о (а„ где а — операция наварной конкатенации слов из двух множеств слов (а,, ...,в„)" и [а„+,)'; 2) для любой помечающей последовательности а Е (.
(й, Х) верно. что (Г» ((и,,..., тн,тч+!), ГДЕ т!, 1 ~/ <П, — ЧИСЛО СРабатЫВаинй ПЕРЕХОДа Гт, а тч~! — число срабатываний всех старых переходов сети й, причем т„+1 не превышает у (пт,,..., птч) . С] Так как класс префиксных языков Х является подклассом классов Х . л Хе и Хе (теоремы 3.1 и 3.3), то можно считать, что граф любого попмнома с целыми неотрицательными коэффициентами можно кодировать описанным в лемме 32 способом с помощью языков нз классов Х.
Хь, Хь. П е м м а ЗЗ Для любой пэры помеченных сетей (И,, Е, ) и (Из, Ез ) ьюэию построить помеченную сеть (И, Х ) такую, что 1[И Х) 1(И$ Еч)Н 1[Из Ез) и 1(И, Е, 0) = 1(Ич, Еы Му, ) О 1(Из, Ез, Му, ), эде МГ и МР— произвольные заданные терминальные разметки первой и второй сетей.
Д о к а з а т е л ь с т в о. Если сети [И,, Е, ) и (Из, Ез ) представлены не в стандартной форме, их следует преобразовать в таковую способом, указанным в доказательстве леммы 3.1. Сеть (И, Е) строится следующим образом: представленные в стандартной форме сети [И,, Е, ) и (Из, Хз) объединяются в одну сеть так, что их включащие места оп, и опз сонме.
щлются в одно место (с одной фишкой в нем) . Если оба исходные сети не содержали л-переходов, то их не будет и в объединенной сети. Последняя удовлетворяет всем требованиям стандартности, а любая порождаеььая ею помечающая последовательность является помечающей последовательностью сети (И,, Е, ) или сети [Из, Ез ) в зависимости от того, переход какой из составляющих сетей первым заберет фишку из объединенного включающего места оп.
Таким обрезом, префиксный и терминальный (для Му О) языки сети (И, Е) являются объединениями соответствующих языков заданных сетей. С) Из леммы 3.3 следует, что классы языков Х, Х~, Хь и Хьо замкнуты относительно операции теоретико. множественного объединения, т.е. язык, полученный объединением любых двух языков из одного из этих классов, также принадлежит этому классу. Т а о р е м а 3.14. Проблемы включения и эквивалентности нерезреши. ьеы для языков сетей Петри иэ классов Х, Х", Хе Хьь.
До к а з ательст в о. Пусть|, и та — два полиномас целыми неотри. цательнымм коэффициентами и требуется узнать, й(У,) ь й(тз). Если бы проблема включения для языков из класса Х была разрешима, то достаточ. но было бы закодировать й(У,) ну [тз) языками 1 (И,, Е,) и [ (Из, Ез) из Х по способу, указанному в лемме 3.2, и выяснить.
1 (ИыЕч) й С. 1 (Иы Ез ) . Зто означало бы, что проблема включения графов полиномов разрешима, что не верно. Поэтому не является разрешимой и проблема включения для языков из класса Х. Так как Х й Х~, Х й Хь и Х С Хь~, то проблема вкпючемия неразрешима н для языков из классов Хь. Хь, Хр". Так как для произвольных двух языков 1, и 1з включемие 1, ъ. 1з имеет мшто тогда и только тогда, когда [., [.) 1з * 1з и каждый из классов языков Х, Х~, Хь, Хь~ замкнут относительно операции объединения, то проблема включения для языков из этих классов легко сводится к проблеме их эквивалентности. Действмтельно, для того чтобы установить справедливость включения [,, ъ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
