Реферат: Дерево непосредственных составляющих

В (7) А и Х находятся в окружении Z и W. Часто эта формула пишется в виде

A --> X êZ — W(8)

Деривация в КНГ начинается с начального символа S и далее идет до тех пор, пока не будет применено последнее правило. Порядок применения правил не важен.

S —> NP VP

NP —> NPR

NP —> DET N

VP —> V VP

VP —> P V NP

NPR —> John, Mary, Bill

N —> paper, man, cow

V —> wanted, meet, want

P —> to

DET —> the

Несколько формальных свойств ГНС:

Если все правила некоторой ГНС G являются контекстно сводными, то G называется контекстно свободной грамматикой (КСГ). Если некоторые правила ГНС являются контекстно зависимыми, то G разывается КЗГ.

Строчный язык некоторой ГНС G определяется как набор всех конечных строк, полученных из G и этот набор обозначается L(G). Строка w считается полученной из G, если w можно получить при последовательном переписывании начального символа S, используя правила грамматики G. Строчный язык L (т.е. набор конечнных строк) называется контексто свободным языком (КСЯ), если существует такая КСГ, что L(G)=L. L называется “строго контекстно зависимым языком”, если не существует такой КСГ, что КСГ, что L(G)=L, и существунт такая КЗГ, что L(G)=L. Заметьте, что грамматика G может быть контекстнозависимой, но ее строчный язык L(G) не обязательно должен быть КЗЯ. Класс КЗЯ включает класс КСЯ. В этом смысле, КЗЯ являются более мощным чем КСЯ.

Однако есть и другой случай, когда КЗЯ не являются более мощными чем КСЯ. Если некоторая КЗГ, G, используется для “анализа”, в этом случае язык анализируемый при поиощи G - контекстносвободный (6, 7). Для того чтобы объяснить использование КЗГ G для анализа данного дерева t, определим анализ t следующим образом. Груба говоря анализ t представляет собой некий срез дерева. Дадим более точное определение: Набор (Pt) для анализа дерева t определяется следующим образом

1. Если t=f (пустое дерево), тогда Pt = f

2. Если t=

A

t0t1 ....tn

тогда Pt={A} v P(t0)P(t1)....P(tn) где t0, t1 ....tn - деревья, А “ . “ обозначает соединение; например:

S

AB

CdE

ce

Pt = {S, AB, AE, Ae, CdB, CdE, Cde,cdB, cdE, cde}

Пусть G - контекстно зависимая грамматика, т.е. ее правила имеют форму

А-->w/p - f