Книжка по сетям Петри (547616), страница 12
Текст из файла (страница 12)
З.б,б покезана помеченная сеть, построенная таким образом по автомату на рис. З.б,а. Простой анализ способа построения помеченной сети по конечному автомату убеждает в том, что язык, допускаемый автоматом, совпадает с терминальным языком построенной сети. Тем самым показано, что Ха С Хо. Однако существуют терминальные языки сетей, не являющиеся регулярными. Например, на рис. З.б,е показана помеченная сеть.
в которой помечающая функция сопоставляет одному переходу символ открывающей скобки [, другому — символ закрывающей скобки ). Для терминальной разметки М~ =0 зта сеть порождает терминальный язык, совпадающий с так называемым скобочным языком, слова которого представляют собой "правильно вложенные" последовательности открывающих и закрывающих скобок. Известно, что скобочный язык является контекстно-свободным )и не регулярным) и задается следующей грамматикой: 8о Зобо. 8о-+ Ро) Зо -.Л. а ь с Здесь ( 1 — символы открываю. щей и закрывающей скобок, Л вЂ” пус- т, т.
г, та т, той символ. Таким образом, клесс а ь с ре улярных языков является собственным подклассом класса Хо. а (, а с, а, б) префиксным регулярным языком называют множество всех слов, являющихся префиксами (в том числе пустыми! слов некоторого регулярного языка. Префмксные ре'улярные языки явлеотся регулярными языками (б) и представляет собой префиксы слов, допускаемых конечными автоматами. Поэтому сеть Петри, построенная по конечному автомату описанным выше способом, порождает префиксный язык, совпадающмй с преФиксным регулярным языком, допускаемым автоматом. Отскща следует, чтоХа йХ С другой стороны, существуют префиксные языки сетей Петри, не являющиеся регулярными.
Например, сеть Петри на рис. З.б,в порождает в качестве префиксного языка так называемый префиксный скобочный язык, слова которого являются префиксами правильно вложенных последовательностей открывающих и закрывающих скобок. Зтот язык задается следующей контекстно свободной грамматикой: 8о '+ 8о8о. 8о (8о) ° 8о + (8о, 8о +Л,П Из теорем 3.1 — З.ч следует, что каждый из классов языков Х, Х, 8о, Хо л л включает все регулярные языки, причем отношение включения является собственным, так как этм классы содержат м нерегулярные языки, такие как скобочный язык или контекстно-свободный язык ( а"Ь" ( и > 0).
Последний порождается как терминальный язык для Мг = (О, О, О, 1( помеченной сетью, показанной на рис. 3.5, з. В качестве примеров нерегулярных языков сетей Петри мы выбрали контекстно свободные языки. Однако не все языки сетей Петри являются контекстносвободными и, наоборот, не все контекстно. свободные языки гюрождаются сетями. Следующие две теоремы подтверждают сказанное.
Т е о р е м а З.б. Существует терминальный язык, порождаемый поев. чвнной сетью Петри и не являющийся контвксно.свободным. Д о к азат е л ь с т в о. Известно, что язык ( а"Ь"с" ( и > О ) не является контакстносвободным. На рис. 3.6 показана помеченная сеть, порождающая этот язык в качество терминального для ДГ~ = (О, О, О, О. 11. П Т е о р е м а 3.6. Существует контвкстносвободныйязсык,лвпорождаамыйниодной (помачакяой1 сетью Патри. Д о к а э а т е л ь с т в о. Рассмотрим контекстносвобсщный язык А в алфавите (а, Ь, с(, порождаемый следующей грамматикой: 8о +8о с8о. 80 а8 8.
88, 8 абЬ, 8 - Л. Зтот язык обобщает скобочный язык, рассмотренный в доказательстве теоремы 3.3, если отождествить а с открывающей скобкой [, Ь вЂ” с закрывающей скобкой ). Символы с как бы разделяют правильно вложенные последовательности скобок. Предположим, что язык Ь порождается некоторой помеченной сетью Петри (В, Х) в качестве терминального языка. Подьязык ( а"Ь"с ( и > 0 ) языка Ь также порождается этой сетью. Тогда эта сеть должна порождать бесконечные последовательности срабатываний. Зафиксируем некоторую бесконечную последовательность срабатываний и соответствующую ей последовательность векторов-разметок. Обозначим через Мг такую разметку, которая возникает после того, как сеть породила префикс г . По пемз ме 2.2 для зафиксированной последовательности разметок существует такая пара чисел ( и/, что 7 чь/ и М~ <М( или М( <Мг. Пусть для определенности М~ < Мр Рассмотрим слово а~Ь с Е Ь.
При достижении разметки М; сеть В порождает префикс а~ этого слова. Рассмотрим слово а~(гс Е Ь. При достижении разметки М; сеть (У порождает префикс а( этого слова. Пусть сеть (У отличается от сети (У лишь начальной разметкой, которая заменена на М~, а сеть В также отличается от В лишь начальной разметкой, которая заменена на М(. Терминальный язык сети ((У, г.) содержит слово Ь с. Терминальный язык сети (Д(, Е) содержит, в силу свойства монотонности языков сетей Петри (теорема 1.1), слово Ьгс, потому что Мг -'~М..
Следовательно, слово а(Ь~с содержится в терминальноы языке сети (У, что противоречит предположению о совпадении этого языка с языком Е. Таким образом, контекстносвободный язык Ь не принадлежит классу Х~о. Поскольку этот класс язывов — максимальный в семействе классов языков, порождаемых сетями Петри (теорема 3.2), то язык Ь не может входить ни в один из классов языков сетей Петри.
П Т ео р ам а 3.7. Класс помеченных сетей Петри строго мошнее класса конечных аетомагое, не сравним с классом магазинных аетомагое и строго менее машан, чем класс машин Тьюринга. До к а з ат ель от во. Теорема является непосредственным следствием теорем 3.1, 3.3 — 3.6. С) з ЗЗ. Разрешимые в веразрмввмые свойства языков сетей Петри Типичная массовая алгоритмическая проблема для формальных языков состоит в том, что требуется установить существование алгоритма, который для произвольного языка Ь, заданного порождающей грамматикой или другой порождающей системой, устанавливает, обладает ли этот язык некоторым свойством.
Например, проблема принадлежност)г связана с проверкой, принадлежит ли произвольное слово а языку Ь; в проблеме пустоты следует выяснить, пусто ли множество Ь; в проблеме конечности задача состоит в выяснении, является ли Ь конечным множеством. Проблемы эквивалентности и включения грамматик или других порождающих языки систем формулируются как проверка равенства ипи включения порохгдаемых ими языков (как множеств) . Известно, что в классе Хг регулярных языков, порождаемых конечными автоматами, все перечисленные проблемы разрешимы. 8 классе контекстно.свободных языков разрешимы проблемы принадлежности, пустоты и конечности, но не разрешима проблема эквивалентности контекстносвобсщных грамматик.
В этом параграфе рассматриваются соответствующие проблемы для введенных вьние классов языков сетей Петри. 47 Т е о р е м а 3.8. Проблема принадлежности разрешима для языков из классов ДЕ и ЕХ. Д о к а з а т е л ь с т в о. Пусть сеть Петри Д( имеет множество переходов Т. Для любого слова т Е Т' легко устанавливается, является ли т последовательностью срабатываний переходов этой сети. Действительно, достаточно проверить. может ли сработать при начальной разметке Ме переход г, символ которого стоит первым в слове г, затем, изменив разметку М„ма М,, где Ме [г ) М,, провери~ь, сможет пи сработать при М, переход.
символ которого стоит вторым в слове т, и т.д. Так как слово т содержит коне~нов число символов, процедура последовательных проверок завершится за конечное число шагов. В любой помеченной сети ((У, Е ! без Х-переходовкаждой помечающей последовательности а соответствует конечное число последовательностей срабатываний таких, что Е(т! а. Поэтому процедура проверки принадлежности слова а префиксному языку А (И, Е ) или терминальному языку (. ((У, Е, Мг) завершается за конечное число шагов. Следовательно. проблеме принадлежности в классах Е и Хе разрешима. Для выяснения принадлежности слова а языку помеченной сети с Х-пере.
ходами может быть применена следующая процедура. Словоа а,аз...а„ длины п. входит в префиксный язык сети (Д(,„, Еь), показанной на рис. 3.7,а. В этой сети Еь (гг ) = аг для 1 < ( ч л и место р„ч, может получить фишку в том и только том случае, если выпопнится последовательность срабатываний с,г, ... г„, порождающая слово а. Пусть ((У, Е)— произвольная помеченная сеть с Х-переходами, для которой выясняется, принадлежит ли а языку (.
(й, Е), Строится новая сеть, получаемая "пересечением" сетей ()У, Е) и (Л/, Еь! гю одинаково помеченным переходам так, как показано на рис. 3.7,б. 8 построенной сети 0У, Е ) место р„ь1 получит фишку в том и только том случае, если в Е (. (Ф, Е) . В предыдущей главе (теорема 2.7) было установлено, что существует алгоритм, с помощью которого можно узнать, получит ли данное место в сети Петри хотя бы одну фишк». Отсюда следует и разрешимость проблемы принадлежности произвольного слова а языку из класса Х ". П Т е о р е м а 3.9.
Проблема досгиэшмосго заданной резмегко в сеш Петро сводима к проблеме пронадлежмосш для языков из класса Хе . До к а з а т е л ь с т в о. Пусть сеть Петри Д(, для которой выясняется вопйос о достижимости некоторой разметки, имеет множество мест Р = =( р,, ры..., р„) и множество переходов т ( г,, гт,..., г„,). преобразуем сеть л( в помеченную сеть ((У', Е ) с Х-переходами следующим образом Ри* 3.8. г, (рис.
3.8) . Все переходы сети д(оставляем непомеченными [они становятся л-переходами в сети (л('. Е)! . новые места и переходы добавляются так, как показано на рис.3.8. Новые переходы г,, гз,..., г„, г„„являются Л переходами, а переходы з г, зз,.... з„помечены символами а,, аз,..., е„из алфавитна А. Начальная разметка новой сети совпадает для мест р,, рз,... ..., р„с начальной разметкой Ме (лэ,, тз, ...,.тч) сети В, место де" имеет одну фищку, места о,,..., оя имеют нулевую разметку.
Пока место де в порожденной сети содержит фищку, зта сеть работает так же, как сеть (У. и достигает некоторой разметки М, после чего может сработать Л-переход г,. С этого момента единственный путь достижения нулевой разметки 0 в новой сети состоит в том, чтобы реализовалась тер- минапьнаЯ послеДовательность сРабатываний т 'г,з, л' гззз л' ... г з„л" г„„, где з л~) означает, что символ перехода 44 входит в т м(л > М(р столько раз подряд, сколько фищек содержит место рэ пРи разметке М.
Последовательность срабатываний т порождает помечающую последовательность а, (л')аэ (л') ... а„(лл) . Таким образом, в построенной помеченной сети имеется возможность кодировать достижимые разметки из множества Я(Д() словами в апфавнтеА и (ОУ, 4„0) =(а~~'а', '...в„" ((т„тз....,тч) ЕЯОУ)) . Следовательно, для выяснения принадлежности некоторой разметки (лэ,, тз...:, т„) множеству Я ОУ) достаточно построить указанным способом помеченную сеть (Д(', Х) и вьюснить, принадлежит ли слово а~'аз ' ... а„" терминальному языку Х (Л('„Е, 01. Сетьра рис. 3.8 прад. ставлена в стандартной форме, поэтому, с учетом леммы' 3.1 и следствия из нее, проблема достижимости разметки может быть сведена к проблеме принадлежности слова к терминальному языку из класса Хее.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
