новые орграфы при помощи следующей

Будем добавлять к множествам S(X) новые орграфы при помощи следующей процедуры до тех пор, пока в S(X) не перестанут появляться новые элементы. Выберем целое p; 1

m и для каждого j, 1

np, выберем орграф D0j

S(Xpj). Затем добавим в S(Xp0) орграф с множеством узлов A(Xpo), обладающий тем свойством, что в нeм дуга от

0 идeт тогда и только тогда, когда в орграфе

(3.5)

существует ориентированный путь из (Xp0;

) в (Xp0;

'): Ясно, что этот процесс рано или поздно закончится и новые орграфы перестанут порождаться, поскольку вообще существует лишь конечное число ориентированных графов. В случае грамматики (таблица 1.1) алгоритм построит следующие множества:

Пусть T - дерево вывода с корнем X, и пусть D'(T) - ориентированный граф с множеством узлов A(X), у которого есть дуга из

' тогда и только тогда, когда в D(T) существует ориентированный путь из (X,

) в (X,

'). Покажем, что после окончания работы описанного выше алгоритма для всех X

V S(X) - это множество всех D'(T), где T - дерево вывода с корнем X 1)

. Действительно, построение не добавляет к S(X) новых ориентированных графов, не являющихся D'(T). Алгоритм можно даже легко обобщить так, чтобы для каждого графа из S(X) он печатал на выходе соответствующее дерево вывода T. Обратно, если T - дерево вывода, мы можем показать индукцией по числу узлов дерева T, что D'(T) принадлежит некоторому множеству S(X). В противном случае T должно иметь вид (3.3) и D(T) "составлен" из

. По индукции и вследствие того, что при j

j' из D(Tj) в D(Tj' ) не проходит дуг вне Dp, дуги в

, составляющей рассматриваемый путь графа D(T), можно заменить соответствующими дугами в

, где

. Поэтому ориентированный граф, включаемый в S(Xp0) на базе

, просто совпадает с D'(T).

Вышеприведeнный алгоритм решает задачу, поставленную в этом разделе.

Теорема. Семантические правила, добавленные к грамматике так, как это сделано в разд. 2, являются корректными тогда и только тогда, когда ни один из ориентированных графов (3.5) ни при каком выборе p и

не содержит ориентированных циклов.

Доказательство. Если (3.5) содержит ориентированный цикл, то, как было показано выше, некоторый D(T) содержит ориентированный цикл. Наоборот, если T - дерево с наименьшим возможным числом улов, такое, что D(T) содержит ориентированный цикл, то T должно иметь вид (рис. 3.3), а D(T) "составляется" из

. Из минимальности T следует, что ориентированный цикл включает по меньшей мере одну дугу графа Dp, и, следовательно, можно, рассуждая, как выше, все дуги, образующие этот цикл и лежащие в одном из графов

, заменить дугами графа (3.5).

Содержание Назад Вперед

Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий