Синтез цифровых автоматов. Захаров Н.Г - 115 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

114
приведет к потере информации и, возможно, к тому, что некоторые свойства сетей
Петри определить будет нельзя, но все зависит от того, как представление было полу-
чено.
Приведение к конечному представлению осуществляется несколькими спосо-
бами. Прежде всего, необходимо использовать те средства, которые ограничивают
введение новых маркировок (называемых граничными вершинами) на каждом шаге.
Для этого могут вводиться пассивные маркировки, то есть маркировки, в которых нет
разрешенных переходов. Такие пассивные маркировки называются терминальными
вершинами. Другой класс маркировок – это маркировки, ранее встречавшиеся в де-
реве. Такие маркировки называются дублирующими вершинами: никакие после-
дующие маркировки можно не рассматривать – все они будут порождены из места
первого появления дублирующей маркировки в дереве. Таким образом, в дереве
на рис. 7.13 маркировка (0, 1, 1), получившаяся в результате выполнения последова-
тельности t
1
, t
2
, t
3
, не будет порождать какие-либо новые вершины в дереве, посколь-
ку она ранее встречалась в дереве в результате выполнения последовательности t
2
из
начальной маркировки.
Каждая вершина может классифицироваться как граничная вершина, терми-
нальная вершина, дублирующая вершина или как внутренняя вершина. Граничными
являются вершины, еще не обработанные алгоритмом, а после обработки они могут
стать терминальными, дублирующими или внутренними вершинами.
Алгоритм обычно начинается с определения начальной маркировки корнем де-
рева, т. е. граничной вершиной.
Пусть х – граничная вершина, которую необходимо обработать, тогда
1) если в дереве имеется другая вершина у, не являющаяся граничной, и с ней
связана та же маркировка, µ(х) = µ(у), то вершина х – дублирующая;
2) если для маркировки µ(х) ни один из переходов не разрешен, то х – терми-
нальная вершина;
3) дуга, помеченная t
j
, направлена от вершины х к вершине у. Вершина х пере-
определяется как внутренняя, вершина у – становится граничной.
Если все вершины дерева – терминальные, дублирующие или внутренние, то
обработка данным алгоритмом останавливается.
Определение. Задача покрываемости. Для заданной сети Петри С с начальной
маркировкой µ и маркировки µ′ определить, существует ли такая достижимая марки-
ровка µ′′ ∈ R(C, µ), что µ′′ ≥ µ. Маркировка µ′′ покрывает µ′.
Это требование можно усложнить, если определять достижимость и покрывае-
мость для множества маркировок, тогда можно перейти к задачам достижимости
множества и покрываемости множества. Однако, если множество конечно, то та-
кие задачи можно решить обычным многократным решением соответствующих задач
достижимости и покрываемости для одной маркировки.
7.4. Моделирование алгоритмов с помощью сетей Петри
Моделирование алгоритмов с помощью сетей Петри имеет ряд особенностей.
Одной из особенностей является свойственные сетям и их моделям параллелизм или
одновременность. В модели сети Петри два разрешенных невзаимодействующих со-
бытия могут происходить независимо друг от друга. Синхронизировать события, пока
это не требуется моделируемой системе, нет необходимости. Но, когда синхрониза-

Страницы