Реферат: Дерево непосредственных составляющих
Деревонепосредственных составляющих (ДНС) обеспечиваает структурное описаниепредложений. Грамматика непосредственных составляющих (ГНС) характеризует ДНС.И то и другое поэтому играют важную роль в обработке естественного языка длясоздания структурных описаний предложения, которые могут быть использованы вобработке систем понимания или порождения речи.
Деревонепосредственных составляющих:
ДНСкодирует иерархическую структуру предложения. Эта информация двух видов:иерархическая структура группирования и синтаксические категории этихгруппирований.
Предложение
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*, содержит узел А, если существует путь от корня до краядерева, и этот путь имеет форму
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 --> 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
Список литературы
Дляподготовки данной работы были использованы материалы с сайта www.ed.vseved.ru/