(ДНС) обеспечіваает структурний опис пропозицій. Граматика безпосередніх складових (ДПС) характеризує ДНС. І те й інше тому грають важливу роль в обробці природної мови для створення структурних описів пропозиції, які можуть бути використані в обробці систем розуміння або породження мовлення.
Дерево безпосередніх складових:
ДНС кодує ієрархічну структуру пропозиції. Ця інформація двох видів: ієрархічна структура групування та синтаксичні категорії цих групувань.
Пропозиція
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 -> PV 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