Питерсон Дж. - Теория сетей Петри и моделирование систем - 1984 (1184511), страница 32
Текст из файла (страница 32)
Это объясняется ограничениями в автомате с магазинной памятью на доступ только к верхнему элементу магазина, тогда как в сетях Петри возможно обращение к любому ее счетчику в любой момент времени. Теперь, когда мы показали, что не все контекстно-свободные языки являются языками сетей Петри и не все языки сетей Петри являются контекстно-свободными, естественно возникает вопрос: что из себя представляет класс языков, являющихся одновременно контекстно-свободными и языками сетей Петри? В настоящее время мы не в состоянии дать полный ответ на этот вопрос, но известна некоторая иифармапия о языках, входящих в пересечение упомянутых классов. Одним подмножеством класса контекстно.свободных языков сетей Петри является класс регулярных языков.
Другим— множество ограниченных контекстно-свободных языков, которые исследовались Гинзбургом [99]. б.б.З. Ограниченные контекстно-свободные языки Контекстно-свободный язык 1. называется ограниченным контекстно-свободным, если в Х е имеются такие слова (строки) шн шею —.э 7ита1 что 1. с ге',тг,. а~' Термин «ограниченныйз относится к конечному числу слов трн гр«,... ...., гв . Гинзбург разработал детально описанную процедуру про. верки свойств ограниченных контекстно-свободных языков. Он заметил, что в то время не было сведений о неразрешимых задачах, касающихся ограниченных коитекстно-свободных языков.
Ограниченные контекстно-свободные языки характеризуются следукхцей теоремой, предложенной Гинзбургом [99, теорема 5.41. Теорема 6.10. Семейство ограниченных контекстно-свободных языков является наименьшим семейством множеств, определяемых следующим образом: 1. Если 1Р' — конечное подмножество Хе, то кт — ограниченный контекстно-свободный язык.
2. Если 97, и йтз — ограниченные контекстно-свободные языки, то И7, 9 11' н 07,'чтз — ограниченные контекстно-свободные языки. 3. Если %' — ограниченный контекстно-свободный язык и х, у Е Е Х «, то (х'рему' [1 Ъ 01 — ограниченный контекстно свободный язык. Глава Б 17В Мы уже показали (равд. 3.3.1), что всякий конечный автоматп, а также всякий регулярный язык и всякое конечное подмножество Хм являются языками сетей Петри. В равд. 6.5.1 и 6.5.2 показано, что языки сетей Петри замкнуты по отношению к конкатенации и объединению. Следовательно, необходимо показать только, что п.
3 также выполняется для языков сетей Петри. С этой целью построим сеть Петри у' = (С', Х, р', г'), порождающую язык (х'%'у')1 ъО) по данным сетям Петри стандартного вида у, =- = (См, Х, р, Е„.), уэ — - (Сю Х, р„, Рэ) и уе = (Св, Х, рв, Рм), порождающим х, у и И7 соответственно. у' объединяет сети Петри у, ую ув и новую позицию р таким образом, что всякий раз после выполнения у в р помещается фишка. Позиция р служит счетчиком числа выполнений сети у .
После ныполиения необходимого числа раз сети у„выполнится ув и, наконец, выполняется повторно у„, удаляя каждый раз одну фишку из р. Поскольку входная строка порождается корректно, только если сеть Петри пуста (за исключением Р', определенного, как рэ), мы уверены, что число выполнений у„и уэ равно. Эта конструкция, иллюстрируемая на рис. 6.14 для х = — аЬ, у = Ь(а + Ь) и В' =- Ьма, показывает, что (х')Ру')1 э.- 0) — язык сети Петри.
Таким образом, любой ограниченный контекстно-свободный язык — это язык сети Петри. Существуют ли контекстно-свободные языки, являющиеся языками сетей Петри, но не являкхциеся ограниченнымиР К сожалению, ответ положителен. Гинзбург показал, что регулярное выражение (а+ Ь)л не является ограниченным контекстно-свободным языком. Так как этот язык — контекстно-свободный язык сети Петри, очевидно, что ограниченные контекстно-свободные языки являются лишь собственным подмножеством семейства контекстно- свободных языков сетей Петри. Кроме того, язык ((а + Ь)+ а"Ь" )л) 1), являющийся контекстно-свободным, не ограничен и не регуляреи. Для полной характеризации множества контекстно-свободных языков сетей Петри необходимы дальнейшие исследования.
Существование и регулярных множеств, и ограниченных контекстно-свободных языков в качестве подмножеств класса языков сетей Петри оказывается полезным, поскольку оба класса языков имеют желательные свойства и некоторые благоприятные для анализа характеристики. 6.6.4. Контекстно-связанные языки Мы исследовали взаимосвязь языков сетей Петри с регулярными языками н с контекстно-свободными языками.
Обратимся теперь к контекстно-связанным языкам. На рис. 6.13 показан язык сети Петри, являющийся контекстно-связанным; мы докажем что все П См. сноску иа с. 174. — Прим. лед. Глава а языки сетей Петри — контекстно. связанные. Поскольку известно, что все контекстно. свободные языки являются контекстно-связанными и существуют контекстно-свободные языки, не являющиеся языками сетей Петри, приходим к выводу, что существуют контекстно-связанные языки, не являющиеся языками сетей Петри.
Следовательно, включение — собственное. Теорема 6Л!. Все языки сетей Петри являются контекстно-связанными. Доказательство того, что все языки сетей Петри являются контекстно-связанными, довольно сложно. Существуют два способа показать, что язык контекстно-связанный: построить контекстно- связанную грамматику, порождающую его„или определить недетерминированный линейно-ограниченный автомат, порождающий этот язык.
Питерсон (2361 показал, как определяется контекстно-связанная грамматика, порождающая язык сети Петри. Здесь мы по. казываем как линейно-ограниченный автомат может породить язык сети Петри. Линейно-ограниченный автомат подобен машине Тьюринга. Он имеет конечное множество состояний, головку чтения/записи и (бесконечную в обе стороны) ленту. Ограничением, отличающим его от машины Тьюринга, служит то, что длина участка ленты, который можно использовать, ограничивается линейной функцией от длины входной строки. В этом смысле ои подобен автомату с магазинной памятью, порождающему контекстно-свободный язык (поскольку максимальный размер магазина ограничен линейной функцией от входной строки), за исключением того, чтолинейноограниченный автомат имеет произвольный доступ к своей памяти, тогда как магазинный автомат имеет доступ к памяти только с одного конца.
Для порождения языка сети Петри ее можно промоделировать, запоминая после каждого входного символа число фишек в каждой позиции. Какова скорость роста числа фишек как функции от длины входной строки? Рассмотрим число фишек, полученное после г запусков переходов. Это число, обозначаемое с, для последовательности переходов 1п1,,...16 равно С 1 +лл( ! 0(1~ И ~1(1у )() Так как числа ф(р», (0(1?)) и ф(р», !(11)) и, следовательно, $1(11) $ и )0(1г) $ (мощности входного и выходного комплектов) фиксированы для данной сети Петри, то существует максимальное значение разности 1: 1 = шах ( ! 0 (1г) ~ — ~ 1 (1?) ~ ).
лфг Таким образом, с = 1 + ~ ( ( 0(1, ) ~ — ~ 1 (1, ) ~ )( 1 + г 1. Р / 1 Языки сетей Петри (8! Языка тоно О()'-О) Контекстно-сдезамные (Сз) язо нн сетон ИонтЖстнопетрн (риц сбободные (СГ) Реееоернюе (и) Ограноненнме контекстно сбабодные (ЙСГ) Рис. 6.!0. Взаимосвязь языков сетей Петри с традиционными классами языков. Число фишек, а следовательно, и объем памяти, необходимый для запоминания их, ограничены линейной функцией от длины входной строки. Позтому языки сетей Петри могут порождаться линейно. ограниченными автоматами.
Этим доказательством мы показали, что все языки сетей Петри контекстно. связанные. Результаты нашего исследования взаимосвязи класса языков сетей Петри с другими классами нзыков сведены на рис. 6.15 и показаны там в виде графа и диаграммы Венка На рис. 6.16 приведены свойства языков сетей Петри (237, 115]. 6.7. Дененмитеньиые сееденмя Большинство представленных здесь результатов приведены и в (2371 и в 11Щ. Кроме того, Хэк исследовал множество задач разрешимости для языков сетей Петри.
Задача принадлежности (яв- 18? рх р1 Нег Да ? ? Нет Обратному гомоморфнзму Да Заезде Клннн (нтерацян) ? Дополнению Нет Нет Нет Префикс- ные Да Префвкс- ные Да Нет Да Да Нет Да Да Да Да Содержит регулярные языки Снмметрвчеекая разность с контекстно-свободными языками (яе пуста) Контекстно-связанный? Да Да ? Да Да Рнс.
6.16. Свойства некоторых языков сетей Петри (взято нз [237, 1!5)). д 7.' р1 Р ? Р Р Р ? ? Р Р Р ? Р Р Р Н Н ? Н Н Р з Разрешимость задачи Прннадлеж носта Пустоты Конечности Эквивалентности н вклю- чения Рнс. 6.17. Свойства разрешимости языков сетей Петри А- н Р-тнпа (Р— раз- решима, Н вЂ” неразрешнма). ляется строка сс элементом языка Е(у)?) разрешима, тогда как задача пустоты (является язык Цу) пустым?), как легко видеть, эквивалентна задача достижимости.
Неразрешимы задача равенства двух языков сетей Петри и задача нх включения. Этн результаты сведены на рис. б.17. Другой подход к изучению сетей Петри с использованием теории формальных языков рассматривался в [б)1. Онн заметили сходство между запуском переходов и применением правил порождения в выводе, понимая позиции как иетермииальныесимволы, а фишки — как отдельные экземпляры нетерминальных символов. Основное отличие заключается в отсутствии в сетях Петри информации об упорядочении, которая содержится в выводе в виде предложений. Оно привело к определению камнутагпивиьх грамлгшпил, Замкнутость по отноше- нию к Объединению Пересечению Канкатена пни Параллельной композиции Регулярной подстановке Да Да Да Да Да Да Да Да Л-сво- Да бодные Да Да Нет Нег ? Нет Да Да Да Да Префикс ные Да Да Да Да Да ПреФикс- Да Языки сетей ПетРи изоморфных сетям Петри.
Кроме того, в [6Ц рассматривалась взаимосвязь сетей Петри с матричными [Ц, контекстно-рассеянными, нетермннально-ограниченными языками; языками, ограниченными по выводу; равноматричными языками и языками Сцнларда. Нетрудно видеть, например, что класс 1У совпадает с множеством языков Сцнларда матричных контекстно-свободных языков [64, 13Ц. 6.8. Замечания н литературе Имеются три хороших исследования языков сетей Петри: работы [237, 2381, вероятно, менее труднодоступные, чем [1151 (последнее исследование более строгое и полное); [6Ц вЂ” очень труднодоступная, но прекрасная работа, хорошо продуманная и изложенная. 6.Р. Темы для дальнейшего изучения Хотя в исследовании свойств языков сетей Петри сделано уже немало, многое еще предстоит сделать. Из всех определенных классов языков изучены только два — Р- и Е;типа, и они только для обычных сетей.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
