Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 68
Текст из файла (страница 68)
Переход( называется активным, если он не входит ни в какой тупик. Переход называется пассивным, если он не разрешен ни в какой достижимой маркировке. При детальном исследовании активности сети Петри используют также понятие уровней активности. Переход 1 обладает ак)пивностью: уровнл О, если он не может быть запущен (пассивный); уровня 1, если он потенциально запустим, т. е. существует достижимая маркировка, в которой он разрешен; уровнл 2, если для любого целого Й существует последовательность запусков переходов, в которой он присутствует не менее к раз; уровня 3, если существует бесконечная последовательность запусков, в которой он присутствует неограниченно часто; уровня 4, если он потенциально запустим нз всякой достижимой маркировки (т. е.
активен). В сети Петри, изображенной на рис. 4.87, а, переход 18 активен, переходы 81, (э, 14, 1в имеют уровень активности 3; переход гв пассивен. В сети Петри, приведенной на рис. 4.87,6, переход 14 84.11, Мадеаиравание автоматных систем сеаьвми Петри 379 пассивен, переход $8 обладает активностью уровня 1, переход(э— активностью уровня 2, а $1 — активностью уровня 3. Одной из наиболее важных задач анализа сетей Петри являйтся задача достихеимости: достижима ли маркировка )4' из начальной маркировки 7( данной сети Петри? Важность этой задачи обусловлена тем, что маркировка служит интерпретацией состояния системы.
Решение задачи достижимости позволит определить, достижимо ли определенное состояние, будь оно "хорошим" или "плохим" для системы. Описанные свойства и соответствующие задачи анализа сетей Петри наиболее общие, хотя и не охватывают все множество вопросов, которые могут возникнуть при анализе сетей Петри. Для решения задач анализа имеется два основных подхода. Первый Основан на построении дерева достижимости. Дерево достихеи'в(ости — это ориентированное корневое дерево, вершинам кото- $ ого соответствуют возможные маркировки, дугам — переходы. орневой вершине соответствует начальная маркировка.
Из каждой вершины исходят дуги, соответствующие разрешенным переходам. Построение дерева осуществляется последовательно, начиная с корневой вершины; на каждом шаге строится очередной ярус дерева. Например, дерево достижимости для сети Петри, изображенной на рис. 4.87, а, после трех шагов имеет вид, приведенный на рис. 4.88, а (маркировки представлены векторами). Очевидно, что если не использовать при построении дерева определенные соглашения, то активные (даже ограниченные) сети Петри будут иметь бесконечное дерево достижимости. Назовем вершины (и соответствующие маркировки), построенные на очередном шаге алгоритма, граничными. Если в какойпибо граничной маркировке нет разрешенных'переходов, то будем называть такую маркировку терминальной.
Если какая-либо граничная вершина имеет маркировку, уже существующую в дереве, 380 Гл. 4. Теория формальных грамматик и ивн«омв«пов то назовем ее дублируюи1ей. Для терминальных и дублирующих вершин не будем строить исходящих из них дуг. Это обеспечивает конечность дерева достижимости для ограниченной сети Петри (рис. 4.87, а, 4.88, а).
Для неограниченных сетей требуется как-то обозначить неограниченное число фишек в позиции. Пусть и«обозначает такое число, причем и«+ а = и«, и« вЂ” а = и«, а < и«, и«< и«, где о — произвольное целое положительное число. Будем использовать при построении дерева достижимости следуюшее правило. Пусть граничная вершина гя ие является терминальной или дублирующей.
Для каждого разрешенного перехода с в маркировке ,и построим дугу, исходяшую из р. Дугу будем помечать переходом г .. Маркировка,и' новой вершины определяется следующим образом. Если р(р;) = и«, то р«(р;) = и«. Если на путы от корневой вершины к гя существует вершина 1я««такая, чта в результате запуска в р перехода су число фишек в каждой позиции не меньше, чем в 11««, а в позиции р; строго больше, то 11'(рс) = ь1.
В противном случае 1««(р;) — число фишек в позиции р;, получающееся после запуска Гу из,и (рис. 4.88, б). Теорема 4.6. Дерево достилсимости любой сети Петри конечно. Доказательство этого утверждения основано на свойствах и« и на правилах введения этого символа в маркировку граничных вершин. Метод анализа, основанный на дереве достижимости, позволяет определить свойства безопасности, ограниченности, сохранения, исследовать свойства активности и достижимостн. Сеть Петри ограничена тогда и только тогда, когда символ и«отсутствует в дереве достижимости. Кроме того, положение символа и«показывает, какие позиции неограничены. Если символ и«отсутствует в дереве, то число достижимых маркировок конечно, и все вопросы анализа можно решить простым перебором. В частности, для нахождения границы маркировки данной позиции р; нужно найти наибольшее значение 1-й компоненты среди всех вершин дерева.
Если эта граница не превышает 1, то позиция безопасная. Для установления того, является ли сеть Петри сохраняюшей по отношению к некоторому вектору взвешивания И~ = (ю1, и«э, ..., и«„), необходимо решить следуюшую систему линейных уравнений с ограничениями: и ~„,и«йяя'(р;) = в при у = 1, .. н ус, «цн щ>0 при 1=1,...,п, где Й вЂ” число вершин дерева достижимости, которым соответствуют различные маркировки. (Очевидно, что если имеется гяу(р;) = и«, то иц = 0.) 14.11. Моделирование автоматных систем сетями Петри 381 Возможность решения задач активности и достижимости ограничена существованием символа и«, скрывающего конкретную информацию о числе фишек. Например, если в сеть Петри, изобрал1енную на рис. 4.87, б, ввести две дуги (11, рг), (рг, сэ), та полученная сеть Петри будет иметь то же дерево достижимости, что и первоначальная.
При этом в новой сети Петри в позиции рэ может быть только четное число фишек, тогда как в первоначальной сети — любое, т. е. множества достижимости этих сетей Петри не совпадают. Можно привести разные сети с различными свойствами активности, но имеюшие одно дерева достижимости. Тем не менее, хотя дерево достижимости и не дает полной информации о свойствах достижимости и активности, в некоторых случаях оно позволяет ответить на вопросы по достижимости и активности. Например, если в нем имеется терминальная вершина, уо сеть Петри не активна. При решении задачи достижимости может оказаться что маркировка р' присутствует в дереве достн« « димости (положительный ответ) или что маркировка 1л не покрывается никакой вершиной дерева достижимости, т.
е. 11«« ~ уя для всех вершин уь««(отрицательный ответ). Другой подход к анализу сетей Петри называется матричным и основан на их матричном представлении. Введем матрицы В и В+, столбцам которых соответствуют позиции, строкам — переходы, и В (у, 1) = Яр;, У(г )), В+(у, я) = 4(р;, 0(ь' )). пусть е(у) — вектор-строка, компоненты которой соответствуют переходам и все равны нулю, за исключением у'-й, которая равна 1. Тогда переход ь' 'разрешен, когда 11 ) е(у) В (уь рассматривается как вектор), а результатом запуска с из гя является ул« = = 1я — е(у)В +е(у)В+ = р«+е(у) (В+ — В ) = 11+е(у).
В, где В = В+ —  — составная матрица изменений. Маркировка уя«, получаюшаяся из уя в результате запуска последовательности о = 11««1,... ь' „определяется как уя' = 11+ е(у'1)В+ е(уэ)В+... + е(у'1)В = = 11 + (е(у1) +... + е(уь)) =,и + у (а) В, где у (о) = е(у1) +... + е(уь) — вектор запуска, я-я компонента которого равна числу запусков 11, в а. Если маркированная сеть Петри является сохраняюшей по отношению к некоторому вектору взвешивания И«(И' — векторсголбец), то уяИс = 1л«Ис для любой гя' = В(С, р).
Так как яя' = = 11+ у(с«)В, то У(о)ВИ~ = О. Поскольку это верно для всех Х(о), имеем ВИ~ = О. Следовательно, сеть Петри является сохраняющей по отношению к некоторому вектору взвешивания тогда и только тогда, когда имеется такой вектор И', что ВИ« = О. Это уравнение позволяет отыскать и сам вектор взвешивания И'. » l Рис. 4.90 Рис. 4.89 Рис. 4.91 382 Гл.4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
