Питерсон Дж. - Теория сетей Петри и моделирование систем - 1984 (1184511), страница 29
Текст из файла (страница 29)
Теорема 6.1. Всякая сеть Петри эквивалентна сети Петри стандартного вида. ,((оказательстпзо. Доказательство проведем с помощью вспочо- И Р состоит из маркировки, содержащей фишку в ру (если Л т (.(у)) а также маркировки, содержащей фишку в р (если Л Е Ь(у)). — При и. нарев. Гло«о 6 160 Полицие деистеае Начал леди гт ! Рве. 6.5. Приведение сети Петри к стандартному внду. Выполнение втой сети совпадает с выполненвем первоначальной сети. гательного построения. Пусть т = (С, о, 1», Р) — помеченная сеть Петри с С = (Р, Т, У, О).
Покажем, иаи построить эквивалентную сеть т' = (С', о', 1»', Р') с С' =- (Р', Т', Р, О') стандартного вида (рис. 6.5). Прежде всего введем три новые позиции р„рт и р„которых ие было в Р. Пспиция Р, является начальной, р~ — заключительной, а Є— позиция «действия»; для того чтобы запусклюбого перехода в Т был разрешен, в позиции р, должна быть фишка. В начальной маркировке С' будет только одна фишка в Р„. заключительная маркировка будет содержать одну фишку в Р, (если дЕ Цу)) или в рт (если Л ~А(т)).
Теперь необходимо гарантировать, что всякая последовательность переходов в С, приводящая из начальной маркировки в заключительную, повторима в С'. Рассмотрим для этого три типа строк в Е(т). Во-первых, пустая строка учитывается определением Р'. Принадлежность д языку Цу) определяется проверкой того, является ли начальная маркировка р заключительной, 1» Е Р. Во-вторых, для всех строк длины 1 в Е(у) введем в С" специальный пеРеход из Р, в Рг следУющим обРазом: дли а Е Х, такого, что сс 6 Ь(у), определйм 1. Е Т' с 1(Г. ) = (Р,), О(Г„) = (РД. Меткой 1„будет ех.
Установить принадлежность сс языку Цу) можно, рассматривая все переходы Р~ ~ Тс о(1т) = о и проверяя, ие принадлежит ли б(р, (т) Р. Ялики сетей Петри 16« Наконец, рассмотрим все строки длины больше 1. Этн получаются в результате запуска последовательности 1« 1,-" 1, переходов Т.
Нам бы хотелось определить последовательность а1 1 ...1 Ь с новьпни переходами а и Ь. Переход абудетбра ь л тв' л фишку из ра и порождать начальную маркировку р, сети С плк,с фишку в р,. Каждый переход 11 в Т' идентичен переходу 1 в Т за исключением того, что рт является для него входной и выходной. Это позволит нам запретить все переходы в Т' путем удаления фишки из р„. Переход Ь будет удалять фишку из р„уничтожать заключительную маркировку С и помещать фишку в рт. При таком построении фишка будет перемещаться из начальной пгпиции в заключительную только в результате последовательности а1 ...1 Ь, соответствующей последовательности 1; ...1, которая переводит р в заключительную маркировку в С. К сожалению, поскольку в С', но не в С будут присутствовать лишние символы, соответствующие переходам а и Ь, полученная последовательность окажется длиннее.
Выходом из такого положения явилось бы пустое помечение а и Ь, но в языках 1:типа оно неразрешено. Для обхода этой трудности мы вынуждены «слить» ' переходы а и 1- в один переход 1, а переходы Ь и 1- — в перей 11' й ход 11,. Переход в Т для всякого 1, ~ Тспрелеляе'гся следующим образом: Е Вводим в Т' 11 с 1(11) = 1(1,) П (р,) и 0(11) = 0(11) Б (р„). 2. Если 1(11)ы рп (т. е. входы в 1; образуют подмножество«1 начальной маркировки, вследствие чего 1т может быть первым запускаемым в С переходом), вводим в Т' переход 11 с 1(1;) =.
(Р,) 0(1,') = р — 1(1,) + 0(1,) П (р„). 3. Если 0(1,)и р.' для некоторой р' р Г (т. е. 11 может быть последним переходом, запуск которого приводит к заключительной маркировке), вводим переход 11 с 1(11 ) = р' — 0(1,) + 1(1») () В (р„) И 0(«1) = (рт). Помечение а' определяется следующим образом: а' ( 1') = а' ( 1 ') = о' ( 1' ") = а (11). Любая строка а, Е Х,(у) порождается по определению последовательностью 1п,1„,..., 1)„такой, что а(1,„1„,..., 11«) = сс. По пастроению а=а (1 1 ...1.
1. ), П Здесь р рассматривается как комплект, содержащий р(р;) позиций р; для каждого г соответственно, отношение включения рассматривается как отношение над комплектом, а операции — как операции над комплектами= Прим. иерее. П Точнее, подкомплект. — Прим. верее. !62 Глава б Рис.
6.6. Сеть Петри нестандартного вида. Позиция рэ является н начальной, и заключительной. Рис. 6.7. Сеть Петри стандартного вида, эквивалентная сети Петри, приведенной на рис. 6.6. поэтому са Е Е(у). Следовательно, Цу) =- л.(у') и сети у и у' эквивалентны. Сеть у' имеет по построению стандартный вид.Г, На рис. 6.6 приведена простая сеть Петри, не имеющая стандартного вида. Применение к этой сети Петри конструкции из доказательства приводит к сети Петри, показанной на рис. 6.7. 6Л. Свойства замкнутости Перейдем к изучению свойств замкнутости языков сетей Петри по отношению к некоторым видам композиции (объединению, пересечению, конкатенации, параллельной композиции, и подстановке) и по отношению к некоторым операциям (обращению, дополнению и бесконечной конкатенации). Изучение этих свойств интересно по двум причинам.
Во-первых, оно увеличивает наши знания о свойствах и ограничениях языков сетей Петри как языков. Во-вторых, многие из перечисленных типов композиции отражают процесс композиционного проектирования и конструирования больших систем из малых, поэтому данное исследование может оказаться полезным для разработки методов синтеза. 163 Языка сетей Петли Большинство из свойств замкнутости касаются композиций языков сетей Петри. Рассмотрим два языка сетей Петри, !.~ и Ьэ.
Мы знаем, что каждый из них порождается некоторой сетью Петри стандартного вида. Поэтому можно рассматривать две помеченные сети Петри стандартного вида, ус =- (С,, аь рь Р~) и у, = (С,, а„р„Гд, с !., = !,(у,) и у, —. !.(уе). Поскольку сети стандартного вида, у, имеет начальную позицию р., ~Рь а уе — р., ч ~Р,. Кроме того, Г, = (р,„ри) или (ри) а Ре = (рь Р~,) или (р~,). Покажем, как из этих двух помеченных сетей строится новая помеченная сеть Петри у' = (С', а', р', Р') с языком !.(у'), который является композицией !., и !.е требуемого типа. Описываемые конструкции будем иллюстрировать примерами сетей Петри. Начнем рассмотрение свойств композиции языков сетей Петри с конкатенации, объединения, пересечения и параллельной композиции.
Затем исследуем обращение и дополнение языка сети Петри и, наконец, подстановку. 6.5.1. Конкатенация Многие системы представляют собой последовательную композицию двух подсистем. Каждую из подсистем можно представить сетью Петри со своим языком. При последовательной комбинации двух систем соответствующее выполнение является конкатпенапией выполнения из первого языка сети Петри и выполнения из второго. Конкатенация двух языков формально определяется как !-!4=(х,хэ! х,Е!те хэ6! ). Теорема 6.2.
Если !., и !.е — языки сетей Петри, то !.,!.е — язык сети Петри. Датсаэатеяьопеа. Определим у' таким образом, чтобы заключительная позиция у, совместилась с начальной позицией у,. Тогда переход, памещающий фишку в рц, будет свидетельствовать о конце выполнения уь а также о начале выполнения у,. Любая строка конкатенации у, и 1,е является тогда путем из р„в рт, = р,, и затем в р~, в у' и, следовательно, элементом !.(у'). Аналогично, если строка порождена сетью С', она является конкатенацией строки, порожденной уо и строки, порожденной у. Формальное определение у' учитывает пустую строку и поэтому более сложно, у' можно определить как объединение у, и у, со следующими дополнительными переходами. Для всякого !э~ Т, с ! (ут) = (р,,) вводим новый переход г; с !'(!с) =-- (ри) и О'(!!) =- = О,(!т).
Если рь р Р„то вводим также у~ с !'(ут-") = (р„) и о(у,").= о,(у,). ' Помечение определяем, как о'(у~') = ае(у,) и о'(1;") = ае(ут). Новое заключительное множество Г' = Р, 0Р„если р. ~Р„ в противном случае Р = Р,. ГЗ 6е аю Ь аЬ ь(С,)-(а+Ь) Ь цс )= пайк(л а)) а,Ь д Х(С)=(а+Ь) и"Ь"(ли)) Рис. 6,6. Конкатенация двух яаыков сетей Петри. (Каждый переход в Ст фактически является ~ парой параллельных конфликтующих переходов, помеченных а и Ь соответственно. — Прим. ред.) Из этой теоремы следует, что квасе языков сетей Петри замкнут по отношению к конкатенации. На рис.
6.8 показывается описанная конструкция для Р., = (а+ Ь)" и Еа = а'д . 6.5.2. Обьединение Другой общепринятый метод композиции систем — обаединлние. В композиции такого вида будет выполняться любая, но только одна из подсистем. Эта обычная композищея языков аналогична 165 Языка сетей Петри объединению множеств и определяется следующим образом: Е () Ез = (х! х Е Е или х Е Ее). Теорема 6.3. Если Е~ и Е,— языки сетей Петри, то Е, о Е,— ' язык сети Петри. Доказательство.
Доказательство аналогично доказательству предыдущей теоремы. Определим новую сеть Петри у', такую, что Е(у') = Е, 11 Ее , В новой сети Петри две начальные позиции объединены в одну новую начальную позицию. Первый запускаемый переход удаляет фишку из начальной позиции, после чего либо сеть Петри у, (если переход был из Т,), либо сеть Петри у, (если переход был из Тт) будет действовать в точности так же, как до объединения. Формально мы определяем новую начальную позицию р, и новый переход 1«, для каждого 8;, р Т, с 1(1;,) = (р„) и для каждого 1„р Т» с 1(11,) = (р,,): Р(1т,) = (р,), Р(1т,) = = (р,) и 0'(1~,), = 0,(1ь), 0'(1т,) = 0»(1ы). Функция помечения: о'(1,,) = о,(тн) и о'(1т,) = ое(1т„).
Новая начальная маркировка содержит одну фишку в р,', новое множество заключительных маРкиРовок Р' = Р, 11Р». Если Ри ЕР~ или Р., ЕР„то, кроме того, р, Е Р'. (:." На рис. 6З показана описанная конструкция для Е, = а(а+ ' + Ь)Ь и Е = аыь'(т ~ п ъ 1). 6.5.3. Параллельная композиция Еще один способ композиции двух сетей Петри заключается в разрешении одновременного выполнения двух'систем. Он допускает все возможные «перемешивания» выполнений одной сети Петри с выполнениями другой. Для представления такой параллелыюй композиции Риддл 12Щ ввел оператор )~, который определяется для а, Ь р Х, и хь х, Р Х* следующим образом: ах,!! Ьх, = а (х, а Ьх») + Ь (ах, ~! х»).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
