|
1 0 1 следовательностыо о, можно создать произвольно большее число фишек, просто повторяя последовательность а столько, сколько это нужно. В сети Петри можно запустить переход / столько раз, сколько необходимо для того, чтобы получить произвольное число фишек в р2. Представим бесконечное число маркировок, получающихся из циклов такого типа, с помощью специального символа со, который обозначает «бесконечность». Для любого постоянного а определим со + а = со, а < со. со — а = со, со < со. Для построения дерева достижимости необходимы только эти операции над со. ОАО) (0,ы,1) Рисунок 4.7 Дерево достижимости сети Петри Теперь можно точно сформулировать действительный алгоритм построения дерева достижимости. Каждая вершина i дерева связывается с расширенной маркировкой р[/]; в расширенной маркировке число фишек в позиции мо |
189 тельность запусков переходов <т, начинающуюся в начальной маркировке р и кончающуюся в маркировке р', р'>р. Маркировка //' совпадает с маркировкой р, за исключением того, что имеет некоторые «дополнительные» фишки в некоторых позициях, то есть р' = р+(р'-р) и (р!-у)>0. Теперь, поскольку на запуски переходов лишние фишки не влияют, последовательность о можно запустить снова, начиная в р', приходя к маркировке р\ Так как действие последовательности переходов а добавило р'-р фишек к маркировке р, она добавит также р'-р фишек и к маркировке р\ поэтому р” = р'+(р'-р) или р” = р+2(р’-р). В общем можно запустить последовательность а-п раз, получив в результате маркировку р+п(р’-р). Следовательно, для тех позиций, которые увеличивают число фишек последовательностью сг, можно создать произвольно большее число фишек, просто повторяя последовательность а столько, сколько это нужно. В сети Петри на рисунке ..., например, можно запустить переход tj столько раз, сколько необходимо для того, чтобы получить произвольное число фишек в р2. Представим бесконечное число маркировок, получающихся из циклов такого типа, с помощью специального символа со, который обозначает «бесконечность». Для любого постоянного а определим со + а = со,а<со. со-а = со,со < со. Для построения дерева достижимости необходимы только эти операции над со. 190 о дм» (О.**#, 1> Рис. 5.18. Дерево достижимости сети Петри Теперь можно точно сформулировать действительный алгоритм построения дерева достижимости. Каждая вершина / дерева связывается с расширенной маркировкой //[/]; в расширенной маркировке число фишек в позиции может быть либо неотрицательным целым, либо о. Каждая вершина классифицируется или как граничная вершина, или как внутренняя вершина. Граничными являются вершины, которые ещё не обработаны алгоритмом; алгоритм превратит их в терминальные, дублирующие или внутренние вершины. Алгоритм начинает с определения начальной маркировки корнем дерева, то есть граничной вершиной. До тех пор пока имеются граничные вершины, они обрабатываются алгоритмом. Пусть х граничная вершина, которую необходимо обработать. 1. Если в дереве имеется другая вершина у, не являющаяся граничной, и с ней связана та же маркировка, ц[х\=ц\у\, то вершина х дублирующая. 2. Если для маркировки /4*] ни один из переходов не разрешён (то есть s{p[x\tj) не определено для всех /уеГ), то л: терминальная вершина. |