Грамматика сложения деревьев

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Грамматика сложения деревьев (англ. Tree-adjoining grammar (TAG)) — это формальная грамматика, придуманная Аравиндом Джоши (англ.). Эта грамматика обобщает контекстно-свободную грамматику тем, что элементарной единицей в правилах вывода являются деревья, а не отдельные символы. Таким образом грамматика определяет правила замены узлов дерева на поддеревья (см. дерево в теории графов и дерево в информатике).

История[править | править вики-текст]

TAG возникла как результат исследований Джоши и его студентов семейства грамматик присоединения[1]. Грамматики присоединения хорошо подходят для разбора фраз, включающих основное слово и множество зависимых, сужающих смысл основного, слов (например, «очень большой дом»). Однако они недостаточно ясно характеризуют фразы, в которых ни одно слово не может нести функцию всей конструкции. То же самое относится к грамматике с фразовой структурой. В 1969 году Джоши представил семейство грамматик, которое использует эту взаимодополняемость путем смешивания двух типов правил. Это семейство не является частью иерархии Хомского[2] и относится к слабо контекстно-зависимым грамматикам, то есть по порождающим свойствам сильнее контекстно-свободных грамматик, но слабее контекстно-зависимых[3]. Грамматики сложения деревьев слабо эквивалентны линейным индексированным грамматикам, комбинаторным категорным грамматикам и заголовочным грамматикам[4] (для любой грамматики сложения деревьев можно сконструировать соответствующую ей грамматику из любого из этих трёх семейств, которая будет порождать те же строки).

Описание[править | править вики-текст]

Правило TAG — это дерево с узлом-листом, к которому может быть прикреплено слово (LTAG).

Есть два вида деревьев: «начальные» (часто обзначаются как '\alpha') и «вспомогательные» ('\beta'). Начальные деревья представляют основные валентности фразы, в то время как вспомогательные деревья позволяют использовать рекурсию[5]. У вспомогательных деревьев верхний узел и узел-лист помечены одним и тем же символом.

Замены начинаются с начального дерева и производятся путём замещения или присоединения. Замещение заменяет узел на дерево, верхний узел которого помечен тем же символом, что и заменяемый. Присоединение вставляет вспомогательное поддерево в центр дерева[6]. Вспомогательное дерево должно быть помечено той же меткой, что и узел, к которому оно присоединяется.

Примечания[править | править вики-текст]

  1. Joshi, Aravind; S. R. Kosaraju, H. Yamada (1969). «String Adjunct Grammars» (Proceedings Tenth Annual Symposium on Automata Theory, Waterloo, Canada).
  2. 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).
  3. 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.
  4. Vijay-Shanker, K. and Weir, David J. 1994. The Equivalence of Four Extensions of Context-Free Grammars. Mathematical Systems Theory 27(6): 511—546.
  5. Jurafsky Daniel Speech and Language Processing. — Upper Saddle River, NJ: Prentice Hall, 2000. — P. 354.
  6. Joshi, Aravind; Owen Rambow (2003). "A Formalism for Dependency Grammar Based on Tree Adjoining Grammar". Proceedings of the Conference on Meaning-Text Theory. 

Ссылки[править | править вики-текст]

На английском: