Питерсон Дж. - Теория сетей Петри и моделирование систем - 1984 (1184511), страница 27
Текст из файла (страница 27)
З.З.!) и распознающего автоата (гл. 6). — Прил. ред. ведению сети Петри с множеством начальных маркировок, за исключением того, что каждой последовательности переходов будет предшествовать т~, если до начала выполнения будет использоваться маркировка р;. Мы видим теперь, что эти три определения начальных состояний сети Петри в принципе эквивалентны.
Отходя от традиции, определим язык сети Петри как начинающийся с отдельной маркировки р. 6.3.2. Помечение сетей Петри Как и в случае с начальным состоянием, возможно несколько определений помечения сети Петри. Мы должны определить и алфавит сети Петри, и то, как он связан с сетью Петри. Уже отмечалось, что символы алфавита связываются с переходами, поэтому последовательность запусков переходов порождает строку символов языка. Связь символов с переходами осуществляется функцией полевения о: Т вЂ” ~ Х.
Вариации в определении языка следуют из различных ограничений, накладываемых на функцию помечеиия. Свободно помеченная сеть Петри — это помеченная сеть Петри, в которой все переходы помечены по-разному (т. е. если о(8;) = = о(1т), то т; = 1 ). Класс языков свободных сетей Петри являетси подмножеством класса языков сетей Петри с более общей функцией помечения, в которой не требуются различные метки. Рассматривалась еще более общая функция помечения, допускающая помечение переходов пустым символом, о(тт) =- Л.
Л-помеченные переходы не появляются в предложениях языка сети Петри, и, следовательно, их запуск при выполнении сети Петри не фиксируется. Три класса функций помечения (свободные, без Л- и с Л-переходами) определяют три класса языков сети Петри. Без дальнейшего исследования нельзя сказать, какое из этих трех определений помечения наиболее приемлемо. Возможно, каждое из них является наиболее удачным для некоторого применения. Поэтому мы вынуждены рассмотреть языки, получающиеся при каждом всвможном определении функции помечения. 6.3.3.
Заключительные состояния сети Петри Определение заключительных состояний сети Петри оказывает наибольшее влияние на язык сети Петри. Были предложены четыре основных определения множества заключительных состояний сети Петри. Каждое из них образует свой язык сети Петри.
Одно пз определений взято по аналогии с соответствующим понятием для автоматов — множество заключительных состояний г определяется как конечное множество заключительных маркировок. Этим определением мы вводим класс языков сетей Петри Е- типа. Язики сетей Петли 153 Определение 6.1. Язык 1. является языком сегли Петри /=типа, если существует сеть Петри (Р, Т, 1, О), помечение переходов а: Т-+.Х, начальная маркировка р и конечное множество заключительных маркировок Р, такое, что 1.
= (а(р) е Х" й) 6 Т* и б(р, р) ~Р). Класс языков сети Петри (.-типа является мощным, но свойственное ему требование, что для порождения предложения необходимо прийти точно к заключительному состоянию, противоречит основам подхода сетей Петри.
Это замечание основано патом, что если для маркировки р и перехода 1; определено б(р, 1~), то для любого р' ~ р определено б(р', 1т). Из этого вытекает определение нового класса языков — языков сети Петри 0-типа. Определение 6.2. Язык Е. является языком сети Петри 0-типа. если существует сеть Петри (Р, Т, 1, О), помечение еч Т вЂ” Х, начальная маркировка р и конечное множество заключительных маркировок Р такое, что 1. = (о(р) Е Х')р ~ Т"', и существует р~ Е Р такое, что б(р, р) ~ р~). Третьим классом языков сетей Петри является класс языков сетей Петри Т-типа. Эти языки определяются множеством заключительных состояний, используемым в определении языков (.-типа, и множеством (не обязательно конечным) терминальных состояний.
Состояние р, является терминальным, если 6(ро 1х) не определено для всех 1 е Т. Таким образом, класс языков сетей Петри Т-типа задается следующим образом. Определение 6.3. Язык Е является языком сети Петри Т-типа, если существует сеть Петри (Р, Т, 1, О), помечение о: Т вЂ” ~- Х и начальная маркировка р, такая, что 1, = (а(р)Е Х" Щ Т" и б(р, р) определено, но для любого 1; ~Т, 6 (б(р, р), 1~) не определено). Четвертый класс образован языками сетей Петри Р-глина, множества заключительных состояний которых включают все достижимые состояния.
Эти языки являются префикспыми, так как если а~ Хв является элементом языка Р-типа, то для всех пре- ~' фиксов (3 элемента и (т. е. а = рх для некоторого х~ Х') р яв- '1 ляется элементом того же языка. ,, Определение 6 4 Язык Е, является языком сети Петри Р-типа, если ~, существует сеть Петри (Р, Т, 1, О), помечение оч Т -+. Х и началь', ная маркировка р„такая, что 1. = (а(р)Е Х*фЕ Т' и опреде' лено б(р, р)). 6.3.4. Классы языков сетей Петри В дополнение к четырем классам языков сети Петри, основанным иа различных заданиях множества заключительных состояний, имеются вариации языков, порожденные различными определениями функции помечеиия. На рис.
6.1 приведены 12 классов 154 Глаеа о языков, получающихся в результате комбинаций четырех типов определений заключвтельных состояний и трех типов функций помечения. Каждая клетка таблицы содержит обсвначснне соответствующего класса языков сетей Петри. Гдододиые дел Л еереиодод С Л-оерелодими Ю-тии Т.тии Р-тии Рис. о.!. 12 классов языков сетей Петри. Для задания конкретного языка сети Петри должны быть определены четыре элемента: сеть Петри С = (Р, Т, 1, б); функция помечения о: Т вЂ” л'; начальная маркировка р: Р— Ю; множество заключительных маркировок Р (для языков 1.- и б-типа).
Назовем р .=- (С, о, р, Р) помеченной сетью Петри для сети Петри С, помечения о, начальной маркировки р и множества заключительных состояний Р. Для данной помеченной сети Петри у можно определить )2 языков: 1.(у), б(у), Р(у), Т(у), 1/(у), бр(у), ТР(у), Рт(у), 1. (у), Т"(у), Р'(у).' Различные определения языков сетей Петри связывают с данной сетью Петри различные языки. Рассмотрим, например, сеть Петри на рис. 6.2. На сети задана начальная маркировка (1, О, О, О) и каждый переход 1; помечен о(1е). Если мы определим Р =-= = ((О, О, 1„0)) (одна фишка в позиш1в ра), языком 1;типа будет (а"еЬ" 1п -. 0), языком б-типа — (атсЬ" 1т ~ н =. О), языком Т-типа — (амсЬ"с( 1ео ~ п ~ 0), а языком Р-типа — (ат 1и ~ ъО) 0 (а сЬ" 1от ) и ъО) 0 (отсЬос(ро ъп >0).
Языки всех четырех типов для этого примера различны. Данная функция помечения является свободным помечением, но при использовании других функций помечения можно получить и другие языки. Несмотря на различия в определениях„классы языков сетей Петри тесно связаны. Например, множество свободных помечений включено в множество пе-е-помечений, которое является подмножествозс мнои~ества е.-помечевий. Таким образом, 11 <: — 1. с 1.", Тг а Т а Т", Р1 с Р с Р" . бес= б «=.б', Языки сетей Петри Кроме того, всякий язык Р-типа является языком 6-типа с Р = =- ((О, О, ..., О)). Поэтому Рг с= 6/, Р а 6, Р" а 6".
Можно показать также, что всякий язык типа 6 илн 6" является языком типа х. илн х.э соответственно. Пусть х. — язык 6-типа лля сети Петри (Р, Т, У, О), начальной маркировки р и множества заключительных состояний Г. Построим новую помеченную сеть Петри с теми же позициями, но с дополнительными переходами, определенными следующим образом: р с Рэ Ра Рис.
6.2. Сеть Петри, яллюстрээруюпэая различные классы языков. Каэкдытэ переход помечается меткой. Пусть для каждого Рэш Т В; означает множество всех собственных подкомплектов О (8э). Всякий подкомплект из В; используется для определения нового перехода, помеченного так же и имеккцего те же входы, что и 1эч но имеющего в качестве выхода этот подкомплект. Эти новые переходы добавляются к первоначальному множеству переходов.
Например, если рассмотреть переход а в сети Петри на рис. 6.2, то его входным комплектом является (рэ), а выходным комп.тектом (Р,, Рт). ПодкомплектамиэЭ (Рэт Ря) ЯвлЯютсЯ (Рэ), (Ра) н О (==- еэ). Этот переход влечет введение в сеть трех новых переходов. Все этя новые переходы будут помечены а и иметь входной комплект (рэ), но выходными комплектами будут три указанных выше подкочплекта (по переходу на каждый подкомплскт). Для переходов Ь, с, сэ также будут введены новые переходы, которые будут иметь те ~ же входы, но пустые выходы (поскольку в имеющейся сети выходы образованы одноэлементными комплектами, следовательно, единственным подкомплектом будет еэ).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
