ISSN 2305-5626. Вестник МГТУ им. Н.Э. Баумана: электронное издание. 2013
4
добна сети Петри: блок-схему изображают в виде узлов двух типов
(принятия решения — графически показано ромбами — и вычисле-
ния — показывают прямоугольниками) и дуг между ними. Удобный
способ выполнения блок-схемы — введение фишки, которая обозна-
чает текущую инструкцию. По мере выполнения инструкций фишка
передвигается по блок-схеме.
Перевод блок-схемы в эквивалентную сеть Петри заменяет узлы
блок-схемы на переходы сети Петри, а дуги блок-схемы — на пози-
ции сети Петри. Каждая дуга блок-схемы соответствует точно од-
ной позиции в сети Петри. Узлы блок-схемы представляют по-
разному в зависимости от их типа: узел вычисления или узел приня-
тия решения.
Фишка, находящаяся в позиции, означает, что счетчик команд
установлен на готовность выполнения следующей инструкции. Каж-
дая позиция имеет единственный выходной переход, за исключением
позиции, которая имеет по два выходных перехода, соответствующих
истинному и ложному значению предиката [2].
Для интерпретации сети Петри необходимо отображать каждый
переход. Следует также отметить, что переходы для вычислений
имеют по одному входу и выходу.
Иерархические сети Петри позволяют анализировать разные
участки алгоритма с различной степенью детализации. Это дает воз-
можность на этапе формализации использовать уже существующие
модели, интегрируя их с разрабатываемой сетью, а также локализо-
вать обнаруженные при анализе ошибки путем уточнения проблем-
ных участков.
Дерево достижимости является одним из методов анализа сети
Петри и представляет множество достижимости сети. Первоначаль-
ная маркировка находится в корневой вершине. Из каждой вершины
исходят дуги, соответствующие разрешенным переходам. Всякий
путь в дереве, начинающийся в корне, соответствует допустимой по-
следовательности переходов. Сеть Петри может иметь бесконечное
дерево достижимости. Для получения дерева, которое можно считать
полезным инструментом анализа, необходимо найти средства огра-
ничения его до конечного размера.
Особенностью алгоритма построения конечного дерева достижи-
мости является специальная классификация маркировок, согласно
которой каждую вершину дерева рассматривают как граничную,
терминальную, дублирующую или внутреннюю вершину.
Граничными
являются вершины, которые еще не обработаны ал-
горитмом, после чего эти вершины становятся либо терминальными,
либо дублирующими, либо внутренними.
Маркировки, в которых отсутствуют разрешенные переходы, яв-
ляются
терминальными
вершинами дерева достижимости. Другой
класс маркировок — это маркировки, ранее встречавшиеся в дереве:
такие маркировки называют
дублирующими
вершинами. Никакие по-
1,2,3 5,6,7,8,9,10