Cтраница 2
Заметим, что существует возможность продвижения по дереву, изображенному на рис. 1, без достижения когда-нибудь концевого узла. Если не существует бесконечных путей в бинарном дереве, то, согласно лемме о бесконечном дереве ( см., например, [5], разд. [16]
Теорема 4.1. Дерево достижимости сети Петри конечно. Доказательство проводим от противного. Допустим, что существует бесконечное дерево достижимости. [17]
В любом случае имеется много способов порождения бесконечного дерева ( таблицы) без привлечения множества Хинтикка. Ключевой проблемой является нахождение систематической процедуры, гарантирующей получение бесконечного дерева, каждая открытая ветвь которого является множеством Хинтикка. [18]
По теореме 4.4.2 G u) может иметь не более одного цикла. Предположим, что такой цикл С ( и существует. В каждой вершине а цикла С ( и будет присоединяться конечное или бесконечное дерево с корнем а -, связывающее вершину а со всеми относящимися к ней вершинами. [19]
Дерево выполнения ( Е - дерево) программы - это дерево, пути которого изображают все возможные последовательности реализации блок-схемы без возврата назад. Если блок-схема не имеет циклов, то соответствующая конечная Е - схема является и Е - деревом. Если же циклы входят в блок-схему, то Е - дерево является бесконечным деревом, в котором каждый повторяющийся путь заменен последовательным повторением поддерева, начинающегося первым узлом вхождения в этот путь. При окончательном упрощении повторяющиеся узлы первого вхождения могут быть исключены. [20]
Обратно, при заданном бесконечном множестве длин, которые удовлетворяют неравенству Крафта, можно использовать построение, выполненное в теореме 3.2.1, чтобы построить код, обладающий свойством префикса. Здесь необходимо сделать два замечания. Первое состоит в том, что так как неравенство Крафта удовлетворяется, то существует конечное множество слов каждой длины щ и поэтому длины могут быть упорядочены; второе состоит в том, что следует начинать ( методически) с полного бесконечного дерева. [21]
Рассмотрим теперь неориентированный граф 0 ( ь определяемый обобщенным циклом Gh. По теореме 4.4.2 Gi может иметь не более одного цикла. Предположим, что такой цикл С ( г существует. В каждой вершине о; цикла О 1 будет присоединяться конечное или бесконечное дерево с корнем ait связывающее вершину а - со всеми относящимися к ней вершинами. [22]