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

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

                      

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

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

Предложение

                        John wanted to publishthe paper.                            (1)

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

                                                                                                                      (2)

   John       wanted     to      publish 

                                                                       the       paper

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

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

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

            S

NP                  VP                  

                                        VP

                                                                              NP                                                          (4)

NPR                V         P          V                                                                                          

                                                                       DET      N

John        wanted     to     publish 

                                                                       the       paper

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

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

[S[NR[NPRJohn]][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

                               t0                           t1        ....               tn

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

                                   S

                        A                     B

            C                     d          E

            c                                  e

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*, содержит узел А, еслисуществует путь от корня до края дерева, и этот путь имеет форму

 r1pА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 имеет место нулевой контекст иэти правила — контекстносвободные. В четвертом и пятом правиле по условиютребуется а слева и узел подчиняется Т (в пятом правиле S).

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

S --> e                         S --> aT1

S --> aT                      T--> aS1

T --> aS                      T1--> 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

NP                  VP

           

NPR                V                                VP

                                                                                                          NP

John                wanted                       P          V                    

+N                  +V                                                                 DET                N

-DET-             +- NP             [to]      publish           

+Animate            .                                          +V                  the                   paper  

                                                                       +- NP + DET +N

                                                                                              +Definite        + DET —

                                                                                                                      +Singilar

Здесь не обсуждается возможность связи комплексныхсимволов и промежуточных узлов.

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

John wanted to publish  the paper

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

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

John saw Mary

                        S

NP

                        AUX                           VP

NPR                                       V                     NP

John                past                 see                   NPK

                                                                      

                                                                       Mary

Mary was seen by John.

            S

NP                  AUX                          VP

NPR

еще рефераты
Еще работы по литературе, лингвистике