Питерсон Дж. - Теория сетей Петри и моделирование систем - 1984 (1184511), страница 31

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 31)

В конце концов обнаружится, что машина остановилась 1т. е. не существует разрешенных переходов). В обычном подходе, когда не имеется отпечатанного выхода, необходимо анализировать текущее состояние машины и проверять, достигнута ли заключительная маркировка. Если она еще не достигнута, мы не принимаем выданную строку и снова пускаем машину. Если же сеть Петри вполне оканчивакицаяся, то нет необходимости анализировать текущее состояние машины, поскольку гарантируется, что заключительная маркировка будет достигнута.

Теперь легко видеть, как можно использовать вполне оканчивающуюся сеть Петри для построения сети Петри, порождакхцей бесконечную конкатенацию ее языка. Мы просто соединяем заключительную и начальную позиции. Поскольку всякий раз, когда фишка появляется'в заключительной позиции, сеть Петри, как мы знаем, бывает пуста, то при повторном использовании сети не будет запущен никакой нежелательный переход.

Зтот подкласс сетей Петри не представляет большого интереса, поскольку можно показать, что между вполне оканчивающимися сетями Петри и конечными автоматами существует взаимно одно- 1 значное соответствие. Следовательно, языки вполне оканчивающихся сетей Петри являются регулярными, и, как уже известно, этот класс языков замкнут по отношению к бесконечной конкатенации. Таким образом, мы убедились, что изучение свойств систем, 173 Языки сетей Патри моделируемых языками сетей Петри, ограничено конечными повторениями подсистем и бесконечными повторениями конечных подсистем. 6.5.8.

Подстановка л1ы уже говорили, что системы можно проектировать и моделировать с помощью сетей Петри иерархическим образом. Это подразумевает сначала спецификацию схемы работы системы на уровне подсистем и затем последовательное уточнение этой схемы путем замены операций на их определения в терминах других операций. В случае применения сетей Петри уточнение может принимать форму подстановю~ целой сети Петри вместо перехода или позиции Последнее не вызывает никаких трудностей, в связи с этим мы ограничим наше рассмотрение задачей подстановки подсети вместо перехода (операции) сети Петри. Подстановку сети Петри вместо операции в другой сети Петри можно рассматривать как композицию языков двух сетей Петри.

Поскольку операция представляется символом из Х, подстлановка языка сети Петри Х, вместо символа о в другом языке сети Петри Х., определяется как замена всех появлений о в Х,, на множество строк Х.. Языки сетей Петри замкнуты по отношению к подстановке, если результат подстановки языка сети Петри есть также язык сети Петри. Вариациями подстановки являются конечнал гюдстановка, прн которой Х., — конечное множество строк, и гомолорфизм, при котором Х,з — одна строка.

К сожалению, вновь результат отрицателен: языки сетей Петри не замкнуты по отношению к обычной подстановке. Это следует из примера подстановки Х. = а"Ь" вместо с в Х., = с '. Причиной опять является возможность повторного запуска сети Петри. В случае же конечной подстановки или гомоморфизма Х. является регулярным языком, следовательно, можно построить вполне оканчивающуюся сеть Петри, порождающую его, из чего вытекают следующие теорема и следствие. Теорема 6.7. Если Х вЂ” регулярный язык, а Х., — язык сети Петри, то результат подстановки Х,, вместо любого символа Х., — язык сети Петри. Следствие 6.2. Языки сетей Петри замкнуты по отношению к ко- нечной подстановке и гомоморфизму. 6.6.

Языки сетей Петри и другие классы языков Рассмотрев свойства языков сетей Петри как класса языков, мы обращаемся теперь к исследованию взаимосвязи между языками сетей Петри и другими классами языков. Рассмотрим, в частности, Глава б классы регулярных, контекстно. свободных, контекстно-связанных языков и языков типа О. 6.6Л. Регулярные языки Одним из простейших и наиболее изученных классов формальных языков является класс регулярных языков. Эти языки порождаются регулярными грамматиками н конечными автоматами н характеризуются регулярными выражениями.

Задачи эквивалентности а Ь цс1=1а"ьа 1л >з) Рис. б32. Коитекстио-свободиый язык сети Петри, ие являющийся регуляриым. и включения дпя двух регулярных языков разрешимы, известны алгоритмы их решения 1130). Такой набор желательных свойств языка сделал справедливым следующее утверждение. Теорема 6.3. Всякий регулярный язык — зто язык сети Петри. Доказательство этой теоремы основано на том, что всякий регулярный язык порождается некоторым конечным автоматом, а мы показали (см. равд. 3.3.1), что всякий конечный автомат можно преобразовать в эквивалентную сеть Петри' >.

Обратная теорема не верна. На рис. 6.12 изображена сеть Петри, порождающая контекстно-свободный язык (а"Ь'~п)1), который не является регулярным. Таким образом, не все языки сетей Петри являются регулярными. 6.6.2. Контекстно-свободные языки Сеть иа рис. 6.12 свидетельствует о том, что не все сети Петри являются регулярными, поскольку язык показанной сети Петри является контекстно-свободным, но не регулярным.

Не все языки сетей Петри являются и контекстно-свободными, о чем свидетель- и В равд. З.З 1 было показано соответствие сети Петри управляющему автомату, соответствие сети Петри распозвающему автомату показывается виалогичио. — Прим. ред. Языки сетей Петри 17о ствует сеть, показанная на рис. 6.13, имеющая контекстно-связанный, но не контекстно-свободный язык.

В отличие от случая с регулярньзни языками существуют также контекстно-свободные языки, не являющиеся языками сетей Петри. Примером такого языка служит контекстно-свободный язык (нярл )те ~ Х"'). На основе этого доказывается следующее утверждение. ЦС1 (иаьяся1я>ОГ Рнс. 6.13. Контекстно-связанный язык сети Петри, не явкяющн йся контекст- но-свободным.

Теорема 6.9. Существуют контекстно-свободные языки, не являющиеся языками сетей Петри. Лаказатпельслма. Допустим, чтосуществует сеть Петри с п позициями и т переходами, порождающая язык няил. Пусть А — число символов в Х, А ) 1. Пусть для входной строки ххл г равно 1х[, т. е. длине строки х. Поскольку возможно й' входных строк х, сеть Петри должна иметь кс различных достижимых состояний, получающихся после запуска г переходов„для того, чтобы запомнить строку х. Если состояний меньше, то для некоторых строк х, и хе 6(Р, х,) = 6(Р, х,), х, Ф х .

Тогда очевидно, что 6(Р, х„хзн) = — 6(6(р,ха),хт) =- 6(6(р,ха),хан) = 6(р,х,хая) Е Г, и сеть Петри будет порождать строку х,хт, которую не должна порождать. й В равд. 4.2.2 мы показали, что для каждого перехода существует вектор ог = еи ° О, такой, что если 6(Я, Фт) определено, то она принимает значение д+ ап Следовательно, после подачи г входных символов, т. е. запуска последовательности переходов Г„Г,,...Й„ получим состояние д,: Ч =Р+Хатг 1 Сумму в выражении можно представить другим способам: % = )а + Хагаи Глава 6 176 где ~~ — число запусков перехода Г~ в последовательности гв,(т, -Лв,Д = К, ~~, ..., ) ) — вектор запуска).

Кроме того, известно, что Хб=г* В лучшем случае векторы пь ц„..., п будут линейно независимы, и каждый вектор запуска (~~, )„..., ),а) будет представлять единственное состояние де. Так как сумма коэффициентов ~~ равна г, вектор Ж, (а, ..., ),а) образует разбиение целого г на т частей. Как показал Кнут 11Щ, чнсло разбиений целого г на т частей равно г+т — 1 Теперь, поскольку < Г+ т — 1 1 (Г+вп — 1) ...

(Г+ 1) ((Г+ т), то в множестве достижимости после запуска последовательностн переходов длины г имеется строго меньше, чем (г+ т)'", достижимых состояний. Тогда для достаточно большого г имеем с «+ т — 11 );(г+ т)'" «й', и, следовательно, невозможно иметь яг различных ссстояннй для всякой из А' возможных входных строк.

Таким образом, никакая сеть Петри не может порождать язык пяпя. П Доказательство этого факта проливает некоторый свет на ограниченность сетей Петри как машин, порождающих языки, и, следовательно, на природу языков сетей Петри. В сетях Петри нет возможности запомнить произвольно длинную последовательность произвольных символов. Из доказательства становится очевидно, что в сетях Петри можно запомнить последовательности ограниченной длины (но зто возможно и в конечных автоматах). Другой особенностью сетей Петри является способность запоминать число появлений символа, как, например, в языке а"(Г"с", в пределах, не доступных для систем, порождающих регулярные н контекстно- свободные языки.

Однако сети Петри не обладают аобъемом магазинной памяти», необходимым для порождения контекстно-свободных языков. Скорость роста пространства достижимых состояний с ростом длины входной строки для сетей Петри комбннаторнап„ но не экспоненциальна, т. е. «объема магазинной памяти» недо статочно. П То есть порядка числа сочетаний иа т по а для некоторых т и и.— Прим. перев. Языки сетей Петри Причина того, что сети Петри способны порождать языки, ко. торые не могут порождаться автоматами с магазинной памятью, несмотря на меньший размер пространства состояний, заключается в более гибких взаимосвязях между состояниями сети Петри по сравнению с ограниченными путями между состояниями в автомате с магазинной памятью.

Характеристики

Список файлов книги