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

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

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

Новая сеть Петри показана на рис. 6.3. Эта новая сеть модифицируется таким образом, что липппэе , фишки, превышающие заключительное состояние из Р, не обязательно будут воспроизведены, если выбирается новый переход, ээ точээее, сабственнымээ подкомплектамп. — Прилэ. перев. ! (Ц ) Глава а имекхций меньше выходов. Таким образом, язык 1.-типа новой сети совпадает с языком 0-типа старой сети.

В описанной конструкции требуется создание новых переходов с теми же метками, что и прежние, поэтому никакого вывода относительно соотношения 6У и И из этой конструкции сделать нельзя. 0 с 1„0' с (.". Рассмотренную конструкцию можно также незначительно модифицировать для того, чтобы показать, что обобщение определения Рвс. 6.3. Сеть Петри, яаык Г-ткиа которой совпадает с языком 6-типа сети Петри, приведенной на рис.

6.2. языка т'.-типа (допускающее неполное задание заключительных маркировок) не изменяет классов Г. и (.т . Пусть заключительная маркировка сети Петри с п позициями является и-вектором над Л' 0 (а). Если са является компонентой заключительной маркировки, то это означает, что мы не должны заботиться о вхождении зиачейия этой компоненты в заключительное состояние.

Состояние з является заключительным, если сущестнует такая заключительная маркировка (, что для всех а, 1 ( с ( и, из ~~ ~- со следует з, = Г,. Это определение более общее, чем да~шее ранее определение языков У.-типа. Рассмотрим сейчас язык, определяемый сетью Петри и не полностью заданной заключительной маркировкой ~.

Пусть т — множество всех позиций, для которых Га =- со. Пусть для каждого ~,Е Т, удовлетворяющего 0(1,) й т+ п, р, = 0(1т) й т и = 0(~,) — рь Комплект р включает все позиции, маркировка которйх не принимается во внимание, тогда как комплект включает все позиции, маркировка которых должна быть задана точно так же, как в заключительной маркировке Г. Введем в сеть новые переходы, их метки и входные комплекты совпадают с метками и вхоДными комплектами Гь а выхоДные комплекты обРазованы т)т + 5, где $ — любой подкомплект рл Эта конструкция действительно не меняет поведения позиций, не входящих в т, но позволяет позициям, непринимаемым во внимание, иметь произвольное число фишек, меньшее или равное числу фишек„которые должны Язеаал сетей Петра быть в первоначальной сети. Таким образом, для каждого предложения обобщенного языка первоначальной сети можно выбрать соответствующие переходы для запуска их в то время, когда сеть достигает такого состояния в, что в; = 1л для ~; =,ь ее, в; = 0 для ) л = ьл.

Следовательно, язык У.-типа для построенной сети Петри с заключительной маркировкой 1'(где все м в не полностью заданной маркировке 1 заменяются на 0) совпадает с обобщенным языком первоначальной сети (т. е. определенным не полностью заданной заключительной маркировкой 1). В случае языков, определяемых множеством не полностью заданных заключительных маркировок (в отличие от единственной такой маркировки, как в только что рассмотренном случае) на основе того, что языки типа Е (и 1.л ) являются замкнутыми по отношению к операции объединения (см. равд. 6.5.2), можно показать, что данные языки остаются еще языками типа Е (или ЕР ).

Вводя не полностью заданные заключительные маркировки, можно показать, что языки Т-типа являются также языками Е-типа (за исключением, быть может, свободных языков Т-типа). Заключительным состоянием )л для языка Т-типа является такое состояние, что никакой из переходов 1; нельзя запустить (т. е. )л ~1(1~) для всех 1~ЕТ). Таким образом, условие, задающее заключительное состояние для языка Т-типа, в точности противоположно условию, задающему заключительное состояние для языка 6-типа.

(Можно назвать язык Т-типа обращением языка 6- " типа.) Нетрудно видеть, что такое множество маркировок может быть описано конечным множеством не полностью заданных маркировок (как это сделано в равд. 5.4). Например, условие (р ~ (2, 0) и )л (1, 1)) эквивалентно (р = (О, ы) или 1л = (1, О)).

Язык Т-типа (или в более общем случае обращение языка 6-типа) можно поэтому представить обобщенным (т. е. не полностью заданным) языком ,1.-типа и, следовательно, языком А-1ипа. Таким образом, Тсэ Е и Тлс:Х.л, Как известно, 11Щ всякий язык Ел-типа можно построить по ' сети Петри, в которой каждый переход имеет входную позицию, и по единственной заключительной маркировке, являющейся нулевой, т. е.

такой, при которой нельзя запустить никакой переход. ,' Бели к каждой позиции добавить Х-переход с одним входом и одним ' выходом, совпадающим с входом (т. е. петлю), то язык не изменится, а нулевая маркировка станет единственной терминальной маркировкой. Следовательно, ЕР ы Т", но из предыдущих рассуждений " Тл ы ЕР, поэтому классы языков эквивалентны, Т" = Е.л . На рис. 6.4 графически представлены соотношения рассмотренных классов языков сетей Петри. Дуга между классами означает включение одним классом языков сетей Петри другого. Глава о Проие0оленое и-ооооодпое потайное помвевние помвеение пвмеввиив Г п,ип Т" — -в- — а- Ф Й 1 Е-пуип Е" — ~- Е е Е.

С-епип С" о о ~ьт ! Р-юип е"~ р — ~- иГ Рис. 6.4. Известные соотношения между классами языков сетей Петри. Дуга из кчасса Л в класс В означает, что класс Л включает класс В. $.4. Свойства языков сетей Петри Исследование языков сетей Петри только начинается, и в настоящий момент сведения о свойствах этих недавно определенных классов языков ограниченны.

Сила сетей Петри отражается в разнообразии классов языков сетей Петри. Новизна исследований объясняет нашу неспособность показать все взаимосвязи между этими языками или обосновать важность только некоторых из классов. Это приводит к широте области исследований, необходимости определения свойств 12 различных классов языков. Очевидно, что все 12 классов языков исследовать в этой книге нев<вможно, поэтому мы ограничимся рассмотрением здесь только одного класса языков сетей Петри, а именно языков Е-типа.

Основными причинами такого решения являются ограниченность объема монографии и то, что этот язык уже исследовался в литературе 1236, 115). Некоторые результаты были получены Хэком [1151 и для префиксных языков (т. е. Р-типа) и будут представлены в нашем заключении. Языки 6- и Т-типа были определены, ио никакой рабоги по их развитию не проводилось. Напомним, что класс языков А-типа включает классы языков Т-, 6- и Р-типа. Таким образом, языки й-типа в некотором смысле образуют наибольший класс языков сетей Петри, и поэтому понятно, почему они исследовались первыми При изучении свойств языков сетей Петри У.-типа обратимся к двум аспектам Сначала представим свойства замкиутосгли сетей Петрин по отношению к некоторым обычным операциям: коикатеП Точнее, языков сетей Петри.

— Прим. левов. Павки сетей Патри !о9 нации, объединению, параллельной композиции, пересечению, обращению, дополнению, бесконечной конкатенации и подстановке. Затем рассмотрим взаимосвязь между языками сетей Петри и классическими формальными языками: регулярными, коитекстно-свободными, контекстно-связаннымп и типа О.

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

Определение 6.5. Помеченная сеть Петри у =- (С, о, р, Е) с языком Е(у), имеющая стандартный вид, )довлетворяет следующим условиям: 1. Начальная маркировка р состоит точно из одной фишки в начальной позиции р„и не имеет фишек в других позициях. р, й 0(1,) ддя всех Г, Е Т. 2. Существует позиция ру Е Р, такая, что а) Р =- (рт) (если Л )(Х.(у)) и Р = (р~, р,) (если Л е Цу)'>; б) ру ~1(1,) для всех 11 Е Т; в) б(р',1,) не определено для всех (, Е Т и р' Е)с(С,р), имеющих в ру фишку (т. е. )т'(рт) ) О).

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

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

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