Питерсон Дж. - Теория сетей Петри и моделирование систем - 1984 (1184511), страница 30
Текст из файла (страница 30)
а!1 Х=Х 1~ а=а. Параллельной композицией двух языков является Е1 ~~ 1 з (х 1~ зз ! х1 рЕ1» херЕ») В качестве простого примера рассмотрим языки Ее = (аЬ) и Е, = (с), язык Е, )) Е, — это (аЬс, асЬ, саЬ). Легко показать, что регулярные, контекстно. связанные языки и языки типа О замкнуты по отношению к параллельной композиции, поскольку параллельная композиция двух конечных автоматов, линейно-ограниченных автоматов или машин Тьюринга Языки сетей Петри 167 являются конечным автоматом, линейно-ограниченным антона~ и машиной Тьюринга соответственно. Вследствие того что пзр лельную композицию двух автоматов с магазинной памятью нел преобразовать в другой автомат с магазинной памятью, контекс,шн свободные языки не замкнуты по отношению к параллельной ко позиции.
Для языков сетей Петри докажем следующую теорему. Теорема 6А. Если Ь, и Š— языки сетей Петри, то «,, 1!У-з.— язык сети Петри. . Доказпшельстпсо. Сеть Петри, порождакхцая параллельную компо. акцию Е, и Ь„строится из сетей Петри, порождающих эти языки.
в ней в качестве начальной маркировки фишки помещаются в на чальные позиции у, и ум новое множество заключительных марки ровок определяется всеми маркировками, принадлежащими Р (в позициях Р,) и Г (в позициях Рз). П Эта конструкция показана на рис. 6.Ю для ь« — — а(а+ Ь)+ и Е =- сйР"сЬ«"с. 6.5.4. Пересечение Как и в случае обьединения, операция пересечения подобна теоретико-множественному определению пересечения и определяется для языков сетей Петри следующим образом: Е, () Е, = (х ~ х Е (; и х 6 Аз). Теорема 6.6. Если ь, и Е, — языки сетей Петри, торч й 1,, — язык сети Петри. Конструкция сети Петри, порождающей пересечение двух языков сетей Петри, несколько сложнее рассмотренных ранее. Всякий раз при порождении строки, когда запускается переход в одной сети Петри, должен запуститься также переход в другой сети Петри с идентичной меткой.
Если в каждой сети Петри существует более одного перехода с одной меткой, необходимо рассмотреть все всаможные пары переходов двух сетей Петри. Для каждой такой пары мы вводим новый переход, который запускается тогда и только тогда, когда запускаются оба перехода в старых сетях Петри. Это достигается взятием в качестве входного (выходного) комплекта но ного перехода суммы комплектов (см. приложение) входных (выходных) комплектов пар переходов старых сетей Петри. Следовательно, если ГгЕ Т, и 1« ~ Тм такие, что о(1 ) = <ф«), то веется переход 1, « ~ Т' с 1'Я,«) =Т«(1,) + 1,(Ф«) и О'(1,,«) = = О,(1,) + Оз(1«). НекотоРые из таких пеРеходов бУдУт иМеть в качестве входов начальную позицию. Если для перехода 16«~ Т', определенного описанным способом, Р(1г «) = (Рч, рч)* то заменяем этот переход на другой 1,',«с !'(~~л) = (Р;).
Эта конструкция, по существу, включает две первоначальные сети Петри Яз»ки сетей ))етяи 169 ь(С1) =се~"са~с А(Гт ) = сат" татаа ИС') = самсвт" с т) семсамс Ряс. 6.11. Пересеяевие двух явмяев сетей Петри. и синхронный режим выполнения. Такая составная сеть порсвкдает пересечение Е, и Е,. Описанная конструкция иллюстрируется на рис. 6.11. 1 6.55. Обреацвнив В отличие от рассмотренных до сих пор операций обращение, но-видимому, представляет только теоретический интерес. Обраие предложения хя — это предложение х, символы которого асположены в противоположном порядке. Мы определяем ату опеаци)о рекурсивное а = а, (ах)а = х"а Глаза 6 170 для а ~ Х, х ~ Х'.
Обращение языка определяется следующим образом: Е~ =(х ~хЕЕ) ° Теорема 6.6. Если Š— язык сети Петри, то и Еа — язык сети Петри. Конструкция в этом случае тривиальна. Начальная и заключительная маркировки меняются местом, меняются местом также входные и выхцдные комплекты каждого перехода. Следовательно, Е(у') = Е(у)л. Построенная сеть просто выполняет первоначальную сеть Петри в обратном порядке и обращает все порождаемые ею строки. 6.5.6.
Дополнение Дополнение Е языка Е над алфавитом Х вЂ” это множество всех строк Х', отсутствующих в Е. Его можно представить как Е = Х~ — Е или Е = (х Р Хв 1 х ~ Е). Эта операция над языком сети Петри может быть полезной прн анализе сетей Петри, так как проверка существования запрещенных состояний или запрещенных последовательностей в дополнении может оказаться легче, чем проверка их несуществования в языке сети Петри. Замкнутость языков сетей Петри Е-типа по отношению к дополнению — задача, которая ждет своего решения. Однако в (64) показано, что некоторые языки сетей Петри не замкнуты по отношению к дополнению, т. е. существуют языки сетей Петри, дополнения которых не являются языками сетей Петри.
65.7. Повторная композиция Мы рассмотрели операции объединения, пересечения, конкатенации, параллельной композиции, обращения и дополнения. Для всех операций, кроме последней, мы описали конструкции, показывающие, что языки сетей Пегри замкнуты по отношению к ним. результаты позволяют сделать следующий вывод. Следствие 6. Е Языки сетей Петри замкнуты по отношению к любому конечному числу выполнений операций обьединения, пересечения, обращения, параллельной композиции и конкатенации, осуществляемых в любом порядке. Доказательство следует из приведенных выше теорем.
Устраняя ограничение на конечность числа разрешенных операций, можно определить новую операцию. Бесконечная конкатенация (звезда Клини) языка — зто множество всех конкатенаций Языки сетей Петри 171 (произвольной длины) элементов языка. Она обозначается через Ь' и определяется как = (.).) и. ()Ш.().... Зта операция может оказаться полезной на практике.
Бесконечная конкатенация подобна моделированию цикла. Кроме того, известно, что регулярные, контекстно-свободные, контекстно-связанные языки н языки типа 0 замкнуты по отношению к бесконечной конкатенации 11301. К сожалению, и весьма неожиданно окааалось, что языки сетей Петри не замкнуты по отношению к бесконечной конкатенации. Зто объясняется конечностью сетей Петри (конечное число позиций н переходов) н разрешакхцей природой изменения состояний (переходы запускать разрешается, но потребовать их запуска нельзя).
Для построения сети Петри, порождающей бесконечную конкатенацию языка сети Петри, потребовалось бы в общем случае повторно использовать некоторую часть сети Петри, что позволяет фишкам появляться и оставаться в некоторых из повторно используемых позиций сети Петри. При последующем повторе эти фишки могут разрешить переходы, которые не должны запускаться. Доказательство того, что сети Петри не замкнуты по отношению к бесконечной конкатенации, оказалась очень сложным. Идею, положенную в основу доказательства, можно продемонстрировать, рассмотрев пример. Ранее показано„чтой"Ь"(л ) 1)'> — язык сети Петри. Ь(ы утверждаем, что (а"Ь")» не является языком сети Петри.
Любая сеть Петри, порождающая (аЧ")*, должна иметь некоторую позицию илн множество позиций, кодирующнх число и для каждой части строки. Зги фишки управляют порождением символов Ь Сеть Петри, парождаихцая (а" Ь")», должна использовать эти фишки более одного раза. Но, поскольку природа сети разрешающая, нельзя гарантировать, что эти позиции станут пустыми перед , повторным использованием. Следовательно, для любой сети Петри, пытающейся породить (а"Ь")», существуют такие 1, 1, А, что сечь Петри порождает также некоторую строку следующего вида: где л, ) ар Основу формального доказательства того, что языки сетей Петри не замкнуты по отношению к бесконечной конкатенации, дал Касараю 1159].
Читатель, знакомый с лингвистической теорией абстрактных семейств языков 11001, легко докажет, что языки сетей Петри не замкнуты по отношению к бесконечной конкатенации. Хорошо известно, что наименьшие полные абстрактные семейства языков замкнуты по отношению к пересечению, а содержащие (а"Ь"1 содержат и всякое рекурсивно перечислимое множество.
Таким аб- П Рисунок В.В для и з- 1. — Прим. нерее. 172 разом, поскольку языки сетей Петри замкнуты по отношению к пересечению и (алб") — язык сети Петри, то, если бы они были замкнуты по отношению к бесконечной конкатенации, они образовали бы абстрактное семейство языков. Однако нам известно, что (ихвл) не является языком сети Петри (см. разд.
6.6.2), поэтому языки сетей Петри не замкнуты по отношению к бесконечной конкатенации. Зта аргументация принадлежит Мандриоли. Тем не менее существует подкласс языков сетей Петри, замкнутый по отношению к бесконечной конкатенации, — это класс языков вполне оканчивающихся сетей Петри. Зто понятие введено в 1104] для моделей вычисления, основанных на сложных билогических графах. Мы заимствуем его определение и переводим в термины сетей Петри.
Определение 6.6. Сеть Петри является вполне оканчивающейся, если всякий раз, когда ее выполнение заканчивается, 1) в сети остается только одна фишка, находящаяся в заключительной позиции; 2) число фишек, находившихся в сети Петри, конечно. Заметим сначала, что вторая часть определения ие обязательна, поскольку если сеть Петри оканчивает выполнение, то делает это за конечное число шагов и, следовательно, порождает только конечное число фишек. Первая же часть определения обязательна. Сеть Петри можно рассматривать как машину, порождакхцую строки символов Мы помещаем фишку на вход машины, и на ленте для нас печатается строка символов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
