Книжка по сетям Петри (547616), страница 30
Текст из файла (страница 30)
длл любого ельтврнвтиаиого разреза 4' а А чети Ииэ услощчя 4'Р 4 следует, что А' е 4. 4 сеть назовем каюткой, если асе ве мекситюльиыв Очщвсети К«пяотиы, и А<ать назовем (. плеткой, воли всв ее мвксимвльиыв Зчюдсвти с чглотиы. А сеть И назовем йгчмотиой, если результатом пересечение жабой мвк. земелькой Очюдсети сети И с жабой мексималыюй Зчюдсетыо сети Н лаллетсл некоторое (вдииставииое1 й сечеиие сети Н. Заметим, что если дпл определеиил поилтий К- и (. елотгюсти в "двуме(лгых" 0- и Знатях требовалась адииставгиюсть злемвита, по которому пересеквютсл свчвиия, то в спу- 114 чае "трехмерной" Асети гюнятие М плотности опрадалпетсл с помощью пересечения -плоскостей" н это пересечение должно бькь сечением. 4 сеть па рнс.
7.6, ° язллепся Мчтлотной, Действительно, ее макснмэлыюл Очюдсеть на рнс.7 б,б пересекается с аз максимепьными Зчюдсетлми н ° рис, 7 б,з и д по йчюченилм (рн гы рз) и соответственно (ры гы рч), а максиммьнаа О подсеть на рнс. 7.6, е пересекаетсл с теми же максимальными Зчюдсетями по 6сеченилм (ры гз~ рзг и соответственно (Рм гъ Рч) ° С другой стороны, 4 сеть на рис. 77, ° не явппатсп Мчглотной, так как яерасечениа ее максимальной О подсети нерпе. 77,з с ее максимальной З.подсетью на рнс.
7.2, е пусто. На рис. 7.6 показаны еще две А сети, из которых одна лаллетсл М плотной (сеть на рнс. 7З, а), другая — неМ плотной (сеть на рис.1й, 6), Орла из максимальных О.подсетей второй сети (рнс. 7.8, е) пересакаатся с одной из максимальных З подсетей этой же сети (рнс. 7.8, г) по линии (ры гз. рг), которэп не явлпетсп Нсачанием сети, так как образует лищь начальный фрагмент 1Мачаннл (рч, гз, рт ° гч. рч ) ° А сеть назовем плояюд, если оне Кчнютне, А плотна, Махотка. На рис. 73, а гюказан пример йпотной сети, а на рис, 73, б — сети, которел не является ни Кч ни р ч ни М щютной.
Возможны резличныа варианты наплотнасти. возникающие за счет резных сочетаний нарущений структурных огранйченнй. Заметим. что если конечность О. или Зчюти гарантировала К- нли (.-плотность этой сети, то конечнал 4 сеть ьюжет оказатьсл не ллотной, но только за счет того, что она не палпетсл Мчеотной. Следующие утверждения иллюстрируют адакаатность 4 сатай как сетевых представлений параллельно еяьтернативных процессов, Незоаам сеть лрееипыюд, есхн длл любой достихммой тупиковой резматки М и дпя любого места р, не принадлежащего множеству хвостовых мест сети, М(р) О.
(Заметим, что бесконечнью 4сетн могут в общем случае не иметь хвостовых мест и/или тупиковьп разметок, В атих случалх они считмотся плавильными.) Л е м м а 74, Любая ацикпическая сеть бвтоласгяь Д о к а з а т ° л ь с т в о. Начальнал разметка 4 сети безопасна по определению.
В силу условия А1$ любое место может иметь ° качестве входных переходоа только альтернативные переходы. Поэтому исключена ситуация, Пнь 2.В. когда некоторое место сети может получить более одной фишки (от па. раллельных яераходов) . О Л а м м а 72. Любая 8свть и любая Освгь являютея правильными Д о к а з а те льет во. В8сети любая достижимая разметка содержит ровно одну фишку, В силу связности 8сети любая тупиковая разметка до. стих|има только в том случае, если единственная фишка сети попадает в хвостовое место. В конечной Осети любой переход сработает ровно овин раз. перемещая фишки из всех своих входных мест в выходные.
Поэтому при достижении тупиковой разметки ни одно иэ мест, не входящих во множество хвостовых мест сети, не может содержать фишек. В бесконечной Осетм нет дости. жимых тупиковых рзаметок, и она по определению — правильная. О Т е о р е м а 7.6. Плотная Алеть является лравильнод.
До к а з а т е л ь с т в о. По определению Мвюотнойсети результатом пересечения любой еа максимальной О-подсети с любой ее максимальной 8.подсетью являетея !)Сечение, Это означает, что любое 1)сечение максимальной О-подсети И ' является одновременно и йсечанием в исходной сети И. Отсюда следует, что любое хвостовое место О-подсети И' является хвостовым местом сати И, а множество хвостовых мест сети И образовано обье. динанием множеств хвостовых мест всех ее максимальных О подсетей. Заметим, что для любой достижимой разметки М в сети И ммохмство мест, содержащих фишки, является еоеечением и существует максимальная О.подсеть, содаржещая зто сечение. Поскольку любая Копотная О.подсеть является правильней сетью (лвм.
ма 7.2), то при любой достижимой тупиковой разметке в плотной сети И любая ее максимальная О.подсеть содержит фишки только в своих хвостовых местах (для этой подсети такая разметка также будет тупиковой) . Следовательно и сеть Исодержит при тупиковой разметке фишки только в своих хвостовых местах. О Т е о р а м а 7.7. В ллогнод А сети любой переход моктвг сработать не болев одною резв и в любом ев а!сечении, состоящем из лврекодов, араба. гыеевт ровно один «арекод. Д о к а з е т е л ь с т а о.
Первая часть утверждения теоремы епревед. лиаз для любой А сети, что следует из ацикличности А сети [условие А4) и ае безопасности (лемма 7.1 ) . Пусть Я вЂ” накоторое ° 1 сечение плотной А сети И, для которой не выпол. нана вторая часть утверждения, т,е. (1) |ю крайней мере деа перехода |, и |, иэ А срабатывают прм функционировании сетм И, или (2) все переходы из А мертвы. В силу ацикличности сети и ее безопасности первый случай возможен, только если переходы |, и |, нзходятея в отношении 1', но тогда они не могут оба входить в А. Второй случай рессмотрмм сначала для частного случая Асетем.
а именно: для 8сетей. Если 8сеть И ~.плотна,то а1сечениа Я пересекаетея со всеми ее 1)сечениями. Поэтому в силу правильности 1. -плотной 8 сати должно существовать !1 сечение, все переходы которого срабатывают, в том чис. ле и переход, входящий в а!сечение А. В общем случаа плотной А сети. если сеть И содержит а) сечение А, ни один из переходов которого не срабатывает, то в И существует макеималь.
ная 8 подсеть И', содержащая зто а) сечение, Пусть (И,, Из,...) — множество всех мексимальмых О.подсетей сети И. Поскольку сеть И плотна и, следовательно, Мплотна, пересечение любой ее максимальной О.подсети 114 Щ с подсетью (У ' образует некоторое йюечение (.р в 1У и одновраьнжно то же йсечение (ч ад(г иМ. Поскольку сеть (уплатив и, сладоватально, 7чвютна, в 8-подсети (У' а1сечениеЯ пересекается с Вюечением А~ по некоторому паре. ходу г;е (.~ Г~ Я. Поскольку сеть (у плотна и, следовательно, к.плотна, то любой переход гг срабатывает в максимальной К«ватной О яодсети Д(~ (теорема 761.
Свободный язык, порождаемый Ячютью (у, является объединением свободных языков всех максимальных Очюдсетей ДГ,, (Уз.... [161, поэтому один из переходов т, ЕЯ обязательно сработатет при функцио. нировании сати (УС) 4 7,6. Развертка сетей Патря в свпьпроцессы В предыдущих параграфах этой главы авадены сетевые представления для трех типов лроцассов — параллельных, последовательно-альтернативных и параллельно альтарнатнвных — и выделаны свойства сетей, адекввно представляющих процессы. Рассмотрим, каким образом можно устано. вить связь между сетями Петри как моделями систем и сетями, описывающими процессы нх функционирования, После установления такой связи можно выделить среди сетей Петри сети, адекватно оеюыаающие "осмысленные" системы, порождеющие "осмысленнью" процессы.
Впадение обобщенных процассов, в которых действия и изменения условий могут быть связаны не только отношениями следования и параллелизма, но н отношениями альтернативы и конкуренции, позволяет ставить вопрос об установлении взаимно однозначного ссютватстеия между сетями Петри и порождаемыми ими сетями. процессами, Когда связь установ. лена, можно следующим образом перенести на сети Патри определения тех свойств, которые были введены для сетей. процессов. Будем говорить, что сеть Петри является илогнг«7 (К., (.чд(.плогной1, если порождаемал аю сеть процесс является плотной (К; (.-, Мчюотной(.
Сопоставлание сети Петри порождаемой сатиюроцесса будет рассматрнваться как результат некоторого преобразования развертки исходной сети. Поскольку сеть, задающая процесс, может быть в общем случае бесконечной, то процадуг а развертки сводится к построению некоторого префикса сети.процесса, заканчивающегося указанием не бесконечноа повторение ав периодического фрагмента. Мы ограничимсл примерами преобразований резввртки для подклассов сетей Петри, порождеощих сати процессы, рассмотренные выше, Заметим, прежде всаго, что для сети Петри, являющейся конечной сетью, удовлетворяющей ограничения А(-А7, преобразованиа развертки тривиально: исходная сеть и порох(даамая ею сеть.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
