О классах категориальных грамматик зависимостей

• Автор: Карлов, Борис Николаевич
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Тверь
• Количество страниц: 103 с.

Оглавление
Введение
1 Основные определения
2 Категориальные грамматики зависимостей
2.1 Нормальные формы
2.2 Свойства замкнутости
2.3 Теорема о представлении
2.4 Автоматы для распознавания КГЗ-языков
3 Мультимодальные категориальные грамматики зависимостей
3.1 Нормальные формы
3.2 Свойства замкнутости
3.3 Неполулинейность
3.4 Сложность распознавания ммКГЗ-языков
Заключение
Литература

Введение
Актуальность. Формальные способы описания синтаксической структуры предложения имеют первостепенную важность для большинства задач информатики, связанных с обработкой информации на естественном языке. После основополагающих работ Н. Хомского, определившего четыре базовых класса порождающих грамматик, был определен еще целый ряд типов грамматик, позволяющих вычислять синтаксическую структуру предложения в ходе его вывода или доказательства его правильности. В частности, грамматики зависимостей (специальный тип грамматик) присваивают структуры зависимостей (структуры подчинения) предложениям языка, который они определяют. Теории синтаксиса естественных языков, основанные на понятии зависимости, имеют давнюю традицию, восходящую к средним векам. Теньер впервые систематически описал структуру предложения в терминах именованных бинарных отношений между словами (зависимостей) [7]. Когда два слова ид и гг2 связаны в предложении посредством зависимости в. (обозначение щ -4 гг2), гщ является главным словом, а и)2 ~ зависимым словом. Содержательно, зависимость (I задаёт ограничения на грамматические и лексические свойства ту и и)2-. на их порядок, контекст и т.п., которые вместе означают, что “гщ управляет гь2”. Например, в структуре зависимостей предложения “Летом здесь играют дети”, приведённой на рис. 1, отношение играют -4 дети показывает предикатную зависимость между сказуемым играют и подлежащим дети. в котором главным словом является глагол.
В этом предложении, как и в большинстве обычных предложений рус-

летом здесь играют дети
Рис. 1: Пример проективной структуры зависимостей
ского языка, структура зависимостей проективная, что, несколько упрощая, означает, что зависимости в структуре не пересекаются. Большинство грамматик, порождающих деревья зависимостей, имеют дело только с проективными структурами. С другой стороны, в языках достаточно часто встречаются предложения, имеющие непроективпые структуры зависимостей.
летом здесь будут играть дети
Рис. 2: Пример непроективной структуры зависимостей в русском языке
Например, использование будущего времени в предложении “Летом здесь будут играть дети” приводит к появлению двух разрывных зависи-
Разрывные зависимости встречаются и в других языках. На рис. 3 изображена структура зависимостей французского предложения “II n’en avait plus besoin” (“Он больше в этом не нуждался”), а на рис. 4 —- английского предложения “The person to whom you must refer is Smith” (“Человек, к которому Вы должны обратиться, — Смит”).
Рис. 3: Пример непроектнвной структуры зависимостей во французском языке
Современная лингвистическая теория синтаксических зависимостей была разработана Мельчуком [37]. Первые точные определения грамматик
обст-вр
мостеи играть —> летом и играть
здесь, показанных на рис. 2.
il n' en avait plus besoin

симостей вида У Таким образом. КГЗ в нормальной форме только
слабо эквивалентна исходной КГЗ.
Пример 2.1. Рассмотрим грамматику С для языка Ь — { апЬпсп п> 0 }. а[3/С/В,[А/В
Ь [ВУА, [АВ}А с нэ [С/С] V, [С] VI
Приведём эту грамматику к нормальной форме, используя предложенную в теореме конструкцию. Сначала построим кс-грамматику — С'Т’(С). Нетерминалами будут все локальные подкатегории: N = { [5/С/В], [5/С], [5], [А/В], [ЛВ], [С/С], [А], [В], [С] }. Теперь выпишем правила вывода. [5/С/В] -э а [5/С] [5/С/В] [В]
[5] [5/С] [С]
[Л/В] -> а И -> [А/В] [В]
[B] -э Ъ?А | [Л][ЛВ]
[АВ] -»
[С/С] ->
[C] -» I [С/С] [С]
Обозначим нетерминалы [5/С/В], [5/С], [Л/В], [ЛВ], [С/С], [5], [Л], [В], [С] через ГО, Х2, ХзУ Х4, Х5,5, Л, В, С соответственно, чтобы упростить обозначения. Грамматика запишется в таком виде.
А1 —э а Х2 >Х[В 5 -э Х2С
Х'з —> а
Л -> Х3В В ах4
Х4 -4