Грамматика сложения деревьев (англ. tree-adjoining grammar, TAG) — это формальная грамматика, придуманная Аравиндом Джоши. Эта грамматика обобщает контекстно-свободную грамматику тем, что элементарной единицей в правилах вывода являются деревья, а не отдельные символы. Таким образом грамматика определяет правила замены узлов дерева на поддеревья (см. дерево в теории графов и дерево в информатике).
История
TAG возникла как результат исследований Джоши и его студентов семейства грамматик присоединения[1]. Грамматики присоединения хорошо подходят для разбора фраз, включающих основное слово и множество зависимых, сужающих смысл основного, слов (например, «очень большой дом»). Однако они недостаточно ясно характеризуют фразы, в которых ни одно слово не может нести функцию всей конструкции. То же самое относится к грамматике с фразовой структурой. В 1969 году Джоши представил семейство грамматик, которое использует эту взаимодополняемость путём смешивания двух типов правил. Это семейство не является частью иерархии Хомского[2] и относится к слабо контекстно-зависимым грамматикам, то есть по порождающим свойствам сильнее контекстно-свободных грамматик, но слабее контекстно-зависимых[3]. Грамматики сложения деревьев слабо эквивалентны линейным индексированным грамматикам, комбинаторным категорным грамматикам и заголовочным грамматикам[4] (для любой грамматики сложения деревьев можно сконструировать соответствующую ей грамматику из любого из этих трёх семейств, которая будет порождать те же строки).
Описание
Правило TAG — это дерево с узлом-листом, к которому может быть прикреплено слово (LTAG).
Есть два вида деревьев: «начальные» (часто обозначаются как ' ') и «вспомогательные» (' '). Начальные деревья представляют основные валентности фразы, в то время как вспомогательные деревья позволяют использовать рекурсию[5]. У вспомогательных деревьев верхний узел и узел-лист помечены одним и тем же символом.
Замены начинаются с начального дерева и производятся путём замещения или присоединения. Замещение заменяет узел на дерево, верхний узел которого помечен тем же символом, что и заменяемый. Присоединение вставляет вспомогательное поддерево в центр дерева[6]. Вспомогательное дерево должно быть помечено той же меткой, что и узел, к которому оно присоединяется.
Примечания
- ↑ Joshi, Aravind; S. R. Kosaraju, H. Yamada (1969). “String Adjunct Grammars”. Proceedings Tenth Annual Symposium on Automata Theory, Waterloo, Canada. Используется устаревший параметр
|coauthors=(справка) - ↑ Joshi, Aravind (1969). “Properties of Formal Grammars with Mixed Types of Rules and Their Linguistic Relevance”. Proceedings Third International Symposium on Computational Linguistics, Stockholm, Sweden.
- ↑ 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. Speech and Language Processing. — Upper Saddle River, NJ : Prentice Hall, 2000. — P. 354.
- ↑ Joshi, Aravind; Owen Rambow (2003). "A Formalism for Dependency Grammar Based on Tree Adjoining Grammar". Proceedings of the Conference on Meaning-Text Theory.
Ссылки
На английском:
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .