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

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

История

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

Описание

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

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

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

Примечания

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. (неопр.) . — Upper Saddle River, NJ: Prentice Hall , 2000. — С. .
Joshi, Aravind (2003). (PDF) . Proceedings of the Conference on Meaning-Text Theory . Архивировано из (PDF) 29 ноября 2020 . Дата обращения: 22 октября 2013 . {{ cite conference }} : Неизвестный параметр |coauthors= игнорируется ( |author= предлагается) ( справка )