Книжка по сетям Петри (547616), страница 23
Текст из файла (страница 23)
Иарархическм еегь — зто сеть„задаваемая структурной (рармулой. Поеледмяя представляет собой формулу сети, катарам строится из терминальных и нетерминальных еимволовепамощью операций мивбры Рагу. пярных сетей и упорядоченного множества апрейиюний негерминальных ее ые алое. Каждое определенна имеет аид э: Я, где э — нетерммнальный символ, А — формула сети. Сладуюшля структурная формула опраделлет иерархическую сеть, показанную на рис. 6.6: (1 ° (и; (т. ж) ), 1 ° (Е) ) и: (1(а, Ь); с) у.
(1 ° Ь; д) ж: ((2х, 4И; е), (2У; е) ) х: (2У; у). Дополнительные контекстные ограничения состоят в следующем. (1) Любой символ, входящий в структурную формулу и не определяемый в ней, является терминальным. Он обозначает простой переход, как и символы а, Ь, с, И. е, У, Д на рис. 66. (2) Каждый нетерминальный символ определяется один раз и не может входить в формулу в правой части своего и последующих определений. Нетерминальные символы и, у, ш, х на рис.
6.6 обозначаот составные переходы,, изображаемые прямоугольниками, внутри которых содержатся сети, задаваемые формулами в 'правых частях определений. Переход т является енугленншн переходом перехода г', а переход т ' является обаемлххпим переходом для перехода т. если: [1) т содержится в правой части определения перехода с, (2) существует цепочка переходов г„г,...,. г» такая, что г, = г '. т» = г и для любого /, гда 2 <( <х, переход ту является внутренним переходом перехода гу К приведенным выше ограничениям добавляется еще одно: (3) Любью два определения нетермииальных символом могут содержать в своих правых частях одинаковые символы, если только они задают переходы, один из которых является внутренним по отношению к другому. Это ограничение гарантирует "хорошую вложенность" составных переходов в иерархической сети.
Переход г охеагиеаег переход т, если г является внутренним переходом г и не существует в сети перехода г такого, что г является внутренним переходом с ' и обьемлххцим для с. Переход т — охватываемый переходом г'. Переходы называется соседями, если они охватывается одним и тем же переходом или не имеют охватывающих переходов. В последнем случае они называются переходами верхнего уровня. Место Р является локальным входным или выходным местом перехода г, если все переходы, связанные с Р, являются соседями г или внутренними переходами соседей перехода с. В противном случае, место р является внешним входным или выходным местом перехода г.
Место р является внутренним местом перехода г, если оно связано толь. ко с внутренними переходами переходе г. Место Р является сторонним для перехода г, если оно не является его внутренним местом, но в г есть внутренний переход, связанный с мютом Р. На рис. 6З переход У является внутренним для переходов ж и х, переход к охватывает 1'.
переходы е, ь и с являются соседями. место ( г)— локальное входное место перехода г и внутрьчнее место в х, место (7, е ) является сторонним для х и внешним выходным местом перехода Г. Иерархическая сеть функционирует, переходя от разметки к разметке, кек и регулярная сеть, но правила функционирования иерархической сети отличаются от соответствующих правил для регулярной сети. Эти различия вызваны наличем составных переходов, срабатывание которых является не мгновенным событием„как в сетях Петри, а составным действием. Поэтому целесообразно говорить не о срабатывании составного перехода, а о его работе. Если связать с функционированием сети (дискретное) время, то можно говорить о том, что составной переход может находиться в одном из двух мстояний — пассивном и активном. Смена пассивного состояния на активное, или активация составного перехода, и смена активного состояния на пассивное, или завершение, являются мгновенными событиями.
Начальное состояние всех переходов — пассивное. Будем считать, что простые переходы также могут быть активны, но их активность мгновенна и активация совпадает с завершением. Переход г может быть активирован, если: (1) он пжюивен, (2» охватываощий его переход активен или г является переходом верхнего уровня„ (3) Ъ'р Б Р: М (р) > Р (Р, г), где Р— множество всех мест в сети. Когда составной переход г активируется, происходит смена текущей разметки М сети на разметку М по правилу 'урб Р: М (Р) М(р) — Р(р,с).
условием завершения составного перехода г служит тот факт, что все его внутренние переходы пассивны и ни один из них не может быть активирован. Когда пе(юход г завершен, происходит сьфна текущей разметки М на разметку М по правилу ФРБ Рг: М (Р) Ме(Р). )ГРБ Р(Рг.
'М(р» = М(Р) + Р(г, р», где Р, — множество внутренних мест перехода г, Р— множество всех мест сети. Другими словами, при завершении составного перехода восстанавливается начальная разметка его внутренних мест, а его выходные места яолучаот дополнительные фишки. Пусть каждому составному переходу г сопоставлены два символа: символ г активации переходе и символ 7 заверцюния перехода. Пусть 91 также в иерархической сети множество ТТ Т, О1 О Т, где'Т, — ммо.
жество простых пареходор, [т — множество символов активации, Т - мно. хаство символов заварщений составных перекосов. В процессе функционирования иерархической сетм разметка М может смениться на разметку М а разупьтата: (1) срабатывания простого яерахода г, т.е. м [т) м ', (2) актмвмроаания составного парехода т, т а. М [гт М ', (3) заверщенил составного пцзехода т, т.е. М[г)М . Разметка М досптжиыа а иерархической сети от разметки М в результата последовательности срабатываний т т„..., ты где т~ Е ТТ, если сущаствует послвдоватапьность разметок М [г, ) М, [гт)... [та) М . Опреде. пения достижимых переходов, огренмченности сети и ее живости из $1.2 переносятся естественным образом на иерархические сети. При опрадепении свободных языков иерархических сетей появляются варианты.
Полным сеобобным языком (. ()У) иерархической сети )У назовем мно. местно всех последовательностей г Б ТТ'. такмх, что существует достижимая в )У разметка М, причем Ма [г) М. Свободным языком (. т ()У) иерархической сети )У будам считать проем. цмю языка ь ()У) на мнознюстао Тт те. множество поспадоватепьностай, помученных удалением симеонов активации и заверцюния составных переходов в яоспедоватапьностях из 6 ((У), Помеченная иерархическая сеть имеет дополнитеяьно [частичную) помачаощую функцию Х." Т, Я, которая метит только простыв пера. ходы. Точно так жа.
как и в % 3.1, опрадепяются префиксный и тармм. напьный языки помеченной иерархичаской сети. 6 бя, Сравмеияа мерзрхнческнх сетей с др)пттмм классамм сетей В атом параграфе будет проведено сравнениа аыразиталзмой мощности класса иерархичаских сетай, класса сетей Петри и их обобщений.
рассмотренных в глава 6. Будет показано, что иерархические сати обпадаот та. кими же моделирующими способ. й ностямн, что и счатчиковый автомат, и, следоватепьно, иерархические сети являются существанным обобщенна ем сетей Петри (и регуяярных сетей). д 6 д Т е о р е м а 6.9.Пюбобрвкур. сиена пе)течисяимыб язык ысмет быта порожден помеченной иерар. хической сетью д Доказательство. ДостатсчА но продамонстрнровать, как е иерар- хических сетях можно промоделировать оператор условного вычитания единицы счатчикового автомата.
На тт рис. 6.7 показан фрагмент сати, модапнрующий оператор есяи х~ чь О й 6 то х~. ~ х~ — 1. Место х, соотват. ствует счетчику хи место р~ прид д нимает "упрзвпяющую" фмщку от фрагмента, соответствующего пре- ат. дьщущему оператору, места р~ и р~ соответствуют альтернативам к, Ф О илц х~ ч О, ровно одно нз них должно получить фишку е результате работы фрагмента, Поепе того как в место р~ поатупает фишка, арабатывает переход г „посылая по фаика е три места ры ры рч.
Еолн маото х~ на содержит фишек, то переход гт не может сработать, а разупьтате чего не смогут еработать ни Гч, ни Гз, т.е, р~ не получит фишки, Соатааной переход и в этом случае пвяяетеп единственным переходом, который может сработать. Поела аго актива.
цни начинает работать анутреннпя сеть, содержащая адинотеанный переход Гз. Если к~ не содержит фишек, то параход Гз не может аработать и аосгае. ной переход и завершается, поаыпая фишку ° место рч. Паапа этого мОжат сработать только переход гч, кэторый направляет фишку ° месторг. Если место к~ содархмт фишки, то могут сработать как переход тз, так и составной переход и, Срабатывание гз посылает фишку в маета рт, после чаго может сработать переход гч, забирающий фишки из мает рт, ра н посылающий фишку в рт. Параллельно о поепедоветельностыо арабатываний пареходов г,, гч актнаируетап составной пареход и. Еепи он начал реботать раньша, чем переход гз, то аго внутраннпп сать функцно.
нируат в результате цнкличаокого повторения срабатываний внутреннего перехода гт. Параход и закончит работу илн после того, как гз заберет адинстаенюую фишку из места х~, илн после того, как переход гч забе. рат фишку из мастера. Поела заверцания составного яерехода мастерз получает фишку, котореп позволяет сработать переходу гт, посылаощему фишку в место р~ . Переход гч не может оработать, так как в атом случае маета р1 рч, рч никогда не могут имать одновременно фишки Таким образом, фрагмент иарархичаакой сати на рно. 6.7 моделнруат оператор уоловного вычитания адиннцьь 0 Из теоремы 63 следует, что класс иерархических сетей равномоцюн клааоам ингибиторных сатей и сетей с приоритетами, введенным в гла.
ве б. Более того, сети любого из атил трах клеаеов аффективно преобра. зуютоя е зквивалантныа оетн из двух других классов (9, 26). Покажем, напзммер, что иарерхнчаекую сеть можно траноформировать в сеть а при. оритетами, которая Ь.эквивалентна исходной сети в следующем вмысла.
Сравниваютая свободный язык иерерхичаекой сати и пзык помеченной аетн с приоритетами (или аати другого типа), причем намечавшая функция длп последней сати имеет внд Е(г) в г ипи Е(г) в Х, т,а. яомечающаи функцип пвляетеп чаатичной. Другиьм словами, так помеченная зать отлнчаэтсп от напомеченной лишь наличием дополнительных Х.переходов, символы которых не используютон при порождении языка сети. Теорема 6.10..()ля любод иерархической гаги аюзпю построить Ьзкеиеамягяую еб сею с приоритеюми. Д о к а з а т е л ° с т а о.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
