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

Дерево конкретных составляющих (ДНС) обеспечиваает структурное описание предложений. Грамматика конкретных составляющих (ГНС) охарактеризовывает ДНС. И то и это потому играют важную роль в обработке естественного языка для сотворения структурных описаний предложения, которые могут быть применены в обработке систем осознания либо порождения речи.

Дерево конкретных составляющих:

ДНС кодирует иерархическую структуру предложения Дерево непосредственных составляющих - реферат. Эта информация 2-ух видов: иерархическая структура группирования и синтаксические категории этих группирований.

Предложение

John wanted to publish the paper. (1)

имеет последующую структуру:

(2)

John wanted to publish

thepaper

Эта структура может быть представлена и в скобочной конструкции:

[[John][[wanted][[to][publish][[the][paper]]]]](3)

(2) и (3) обрисовывают группирование без идентификации составляющих. Такие конструкции Дерево непосредственных составляющих - реферат именуются “скелетом”. Скелеты охарактеризовывают фразу без обозначения вершин дерева. Скелет с обозначением категорий является ДНС, для фразы (1) это будет смотреться так

S

NPVP

VP

NP(4)

NPRVPV

DET N

John wanted to publish

thepaper

“John” являетсяздесьименемсобственным, котороеявляетсятакжегруппойподлежащего, “wanted” и “publish” - глаголы, “to”- предлог (точнееговоря “to” должнобытьназваночастицейиливременем), “the” - детерминатор, “paper” - существительное, “the paper” - группасуществительного, “to publish the Дерево непосредственных составляющих - реферат paper” - группасказуемого, “wanted to publish the paper” - тожегруппасказуемого, инаконец, “John wanted to publish the paper” - предложение.

Соответственно скобочная конструкция (3) будет смотреться так:

[S[NR[NPR John]][VP[V to][V publish][NP[DET the][N paper]]]]](5)

Конструкции (4) и (5) обычно (но не всегда) употребляются в системах обработки естественного языка.

Грамматика Дерево непосредственных составляющих - реферат конкретных составляющих (ГНС)

ГНС состоит из набора нетерминальных знаков (таких как N, V, NP, VP, S и т.д.) и из набора терминальных знаков (таки лексические единицы как John “wanted”, “to”, “publish”, “the”, “paper” и т. д. и из набора правил, которые позволяют переписывать нетерминальные знаки в цепочку терминальных и нетерминальных симвлов Дерево непосредственных составляющих - реферат. Если это переписывание не находится в зависимости от контекста, то это контексто-независимая грамматика (КНГ), в неприятном случае - это контекстозависимая грамматика (КЗГ). Правило перезаписи имеет последующую форму:

А --> Х(6)

где Х - последовательсть терминальных и нетерминальных знаков, а А - нетерминальные.

КЗГ имеет иследующее правило перезаписи:

ZAW --> ZXW(7)

где X, Z Дерево непосредственных составляющих - реферат, W - цепочки терминальных и нетерминальных знаков, а А - нетерминальные.

В (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

где А Î V - S (V - алфавит, и S набор терминальных знаков), wÎ V+ (набор ненулевых строк на огромном количестве V) и p, fÎ V* (набор всех строк на V). Если p и f - равны нулю, то такое правило именуется контекскносвободным. Дерево t именуется Дерево непосредственных составляющих - реферат “анализируемым ” в определениях грамматики G, если для каждого узла дерева t производятся правила G. Контекстно зависимое правило А--> w/p - f

производится для узла А, если строчка соответственная ответвлению от узла А, является w и существует анализ t вида r1pАfr2 , где r1, r2 Î V*. Контекстное условие p - f именуется Дерево непосредственных составляющих - реферат анализом предиката.

Вместе с контекстозависимымми правилами правилами, позволяющими специфицировать “правый” и “левый” контекст, нередко нужно иметь правила специфицирующие “верхний” и “нижний” контекст. Имеем узел А дерева t, область (p - f), p, fÎ V*, содержит узел А, если существует путь от корня до края дерева, и этот путь имеет форму

r Дерево непосредственных составляющих - реферат1pАfr2 (r1, r2 Î V*).

Контекстное условие, связанное с таким “вертикальным” анализом именуется “господствующим предикатом”.

В общем виде правило имеет форму

А -->w/СА

где СА - булева композиция анализа и господствующих предикатов.

Пусть G - конечный набор правил и t(G) - набор деревьев, анализируемый G. Подразумевается, что деревья t(G) - предложения; т.е. корневой Дерево непосредственных составляющих - реферат узел дерева t(G) обозначен исходным эмблемой S, а конечные узлы - терминальными знаками. Покажем, что строчный язык L(t(G)) = {x½x, где х терминальная строчка дерева t, и t Ît(G)} контекстно свободен (7).

Пример: Пусть V = {S, T, a, b, c, e} и S Дерево непосредственных составляющих - реферат = {a, b, c, e}, и G - конечный набор серьезных правил.

1. S -->e

2. S --> aT

3. T --> aS

4. S --> bTc / (a_()) Ù DOM (T_)

5. T --> bSc / (a_()) Ù DOM (S_)

Для правил 1, 2, 3 имеет место нулевой контекст и эти правила - контекстносвободные. В четвертом и 5-ом правиле по условию требуется а слева и узел подчиняется Т (в 5-ом Дерево непосредственных составляющих - реферат правиле S).

Язык, порожденный G, может быть порожден G1:

S --> eS --> aT1

S --> aTT--> aS1

T --> aST1--> bSc

S1-->bTc

Грамматика G1 содержит дополнительные нетерминальные знаки S1 и Т1 для проверки локального контекста при порождении. Просто увидеть, что с помощью S1 и Т1, достигается гомоморфизм, позволяющий рассматривать хоть какое дерево G1 с помощью G Дерево непосредственных составляющих - реферат и назад - хоть какое дерево G имеет гомоморфный прототип в G1. Разглядим снова контекстно зависимое правило (10).

V --> wanted½ -VP

когда (10) интерпретируется как неверное правило, как описано выше, лексема “wanted” возникает над узлом V, только если узел VP находится справа от нее (в дереве, где возникает V). Справа Дерево непосредственных составляющих - реферат от V существует строчка, имеющая VP “анализ”. Контекстно-зависимые правила в КГЗ употребляются для анализа обыденных грамматик, а не есть правила обычного переписывания строк.

Терминальные знаки в ГНС. Ранее момента терминальные знаки были представлены как нереализуемые элементы. Это было изготовлено для простоты изложения. Терминальные знаки представляют собой наборы топологических Дерево непосредственных составляющих - реферат, синтаксических и семантических признаков (4, 8). [В принципе может быть устранить все эти признаки средством введения новых нетерминальных знаков. Но их количество будет очень велико (в соответсвии с огромным количеством всех вероятных композиций этих признаков). Это также повлечет существенное усложнение грамматики]. К примеру, терминальные знаки в (4) заменяются на составные (всеохватывающие Дерево непосредственных составляющих - реферат) знаки и получаем (4’ ).

S

NPVP

NPRVVP

NP

JohnwantedPV

+N+VDETN

-DET-+ - NP[to]publish

+Animate .+Vthepaper

+ - NP+ DET+N

+Definite+ DET -

+ Singilar

Тут не дискуссируется возможность связи всеохватывающих знаков и промежных узлов.

Форма (4’) является структурным описанием (СО) предложения (1):

John wanted to publish the paper

ГНС в трансформационной грамматике (ТГ).

ТГ также не дискуссируются в этой статье. Но принципиально увидеть, что ГНС Дерево непосредственных составляющих - реферат (и деревья НС) играют важную роль в ТГ. Основная мысль состоит в том, что некие структурные описания (СО)описываются в базисном компоненте ТГ, а все другие выводятся из их с помощью особых правил, именуемых трансформациями. Базисным компонентом является ГНС, которая определяет набор деревьев НС. Деревья, приобретенные с помощью трансфомаций Дерево непосредственных составляющих - реферат также являются деревьями НС. Таковой взор на ТГ является традиционным и, естественно, облегченным, хотя и достаточен для данного описания. Так, к примеру, дерево НС для предложения (11), показанное на диаграмме (12) - является базисным. Дерево НС (14) для предложения (13), выходит при применении трансформационного правила.

John saw Mary

S

NP

AUXVP

NPRVNP

JohnpastseeNPK

Mary

Mary was seen by John.

S

NPAUXVP

NPR


desyat-sposobov-nauchitsya-lyubvi-k-sebe.html
desyat-stadij-processa-vizdorovleniya-14-glava.html
desyat-stadij-processa-vizdorovleniya-4-glava.html