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