Грамматика сложения деревьев (Ijgbbgmntg vlk'yunx ;yjyf,yf)
Грамматика сложения деревьев (англ. tree-adjoining grammar, TAG) — это формальная грамматика, придуманная Аравиндом Джоши[англ.]. Эта грамматика обобщает контекстно-свободную грамматику тем, что элементарной единицей в правилах вывода являются деревья, а не отдельные символы. Таким образом грамматика определяет правила замены узлов дерева на поддеревья (см. дерево в теории графов и дерево в информатике).
История
[править | править код]TAG возникла как результат исследований Джоши и его студентов семейства грамматик присоединения[1]. Грамматики присоединения хорошо подходят для разбора фраз, включающих основное слово и множество зависимых, сужающих смысл основного, слов (например, «очень большой дом»). Однако они недостаточно ясно характеризуют фразы, в которых ни одно слово не может нести функцию всей конструкции. То же самое относится к грамматике с фразовой структурой. В 1969 году Джоши представил семейство грамматик, которое использует эту взаимодополняемость путём смешивания двух типов правил. Это семейство не является частью иерархии Хомского[2] и относится к слабо контекстно-зависимым грамматикам, то есть по порождающим свойствам сильнее контекстно-свободных грамматик, но слабее контекстно-зависимых[3]. Грамматики сложения деревьев слабо эквивалентны линейным индексированным грамматикам, комбинаторным категорным грамматикам и заголовочным грамматикам[4] (для любой грамматики сложения деревьев можно сконструировать соответствующую ей грамматику из любого из этих трёх семейств, которая будет порождать те же строки).
Описание
[править | править код]Правило TAG — это дерево с узлом-листом, к которому может быть прикреплено слово (LTAG).
Есть два вида деревьев: «начальные» (часто обозначаются как '') и «вспомогательные» (''). Начальные деревья представляют основные валентности фразы, в то время как вспомогательные деревья позволяют использовать рекурсию[5]. У вспомогательных деревьев верхний узел и узел-лист помечены одним и тем же символом.
Замены начинаются с начального дерева и производятся путём замещения или присоединения. Замещение заменяет узел на дерево, верхний узел которого помечен тем же символом, что и заменяемый. Присоединение вставляет вспомогательное поддерево в центр дерева[6]. Вспомогательное дерево должно быть помечено той же меткой, что и узел, к которому оно присоединяется.
Примечания
[править | править код]- ↑ Joshi, Aravind; S. R. Kosaraju, H. Yamada. String Adjunct Grammars (неопр.). — Proceedings Tenth Annual Symposium on Automata Theory, Waterloo, Canada, 1969.
- ↑ Joshi, Aravind. Properties of Formal Grammars with Mixed Types of Rules and Their Linguistic Relevance (англ.) : journal. — Proceedings Third International Symposium on Computational Linguistics, Stockholm, Sweden, 1969.
- ↑ Joshi, Aravind. How much context-sensitivity is necessary for characterizing structural descriptions // Natural Language Processing: Theoretical, Computational, and Psychological Perspectives (англ.) / D. Dowty, L. Karttunen, and A. Zwicky, (eds.). — New York, NY: Cambridge University Press, 1985. — P. 206—250.
- ↑ Vijay-Shanker, K. and Weir, David J. 1994. The Equivalence of Four Extensions of Context-Free Grammars. Mathematical Systems Theory 27(6): 511—546.
- ↑ Jurafsky, Daniel; James H. Martin. Speech and Language Processing (неопр.). — Upper Saddle River, NJ: Prentice Hall, 2000. — С. 354.
- ↑ Joshi, Aravind (2003). "A Formalism for Dependency Grammar Based on Tree Adjoining Grammar" (PDF). Proceedings of the Conference on Meaning-Text Theory. Архивировано из оригинала (PDF) 29 ноября 2020. Дата обращения: 22 октября 2013.
{{cite conference}}: Неизвестный параметр|coauthors=игнорируется (|author=предлагается) (справка)
Ссылки
[править | править код]На английском: