Tree Adjoining Grammar

Tree-adjoining grammars (TAG), auch Baumadjunktions-Grammatiken, sind formale Grammatiken, die von Aravind Joshi eingeführt wurden und in der Computerlinguistik für die Beschreibung von natürlichen Sprachen verwendet werden.

TAGs ähneln kontextfreien Grammatiken, verwenden aber Bäume statt Symbole als kleinste Elemente. Diese Elementarbäume werden nach festgelegten Regeln, Substitution und Adjunktion, miteinander zu immer größeren Bäumen kombiniert. Am Ende des Prozesses kann an den Blättern des entstandenen Baumes ein Satz als Folge von Worten abgelesen werden. Die Menge der durch eine konkrete Baumadjunktionsgrammatik beschreibbaren Sätze bildet die Sprache dieser TAG.

TAGs werden als schwach kontextsensitiv (mildly context-sensitive) beschrieben; sie sind also stärker als kontextfreie Grammatiken, aber schwächer als kontextsensitive Grammatiken in der Chomsky-Hierarchie. Daher sind sie vermutlich stark genug, um natürliche Sprachen zu erzeugen, aber auch schwach genug, um noch effizient parsebar zu sein.

↑ Aravind K. Joshi, Leon S. Levy, Masako Takahashi: Tree adjunct grammars. In: Journal of Computer and System Sciences. Band 10, Nr. 1, Februar 1975, S. 136–163, doi:10.1016/S0022-0000(75)80019-5 (englisch, sciencedirect.com).
↑ David Jeremy Weir: Characterizing mildly context-sensitive grammar formalisms. University of Pennsylvania, United States Januar 1988 (englisch, acm.org – Dissertation in Computer and Information Science).

[:0-1] Aravind K. Joshi, Leon S. Levy, Masako Takahashi: Tree adjunct grammars. In: Journal of Computer and System Sciences. Band 10, Nr. 1, Februar 1975, S. 136–163, doi:10.1016/S0022-0000(75)80019-5 (englisch, sciencedirect.com).

[:1-2] David Jeremy Weir: Characterizing mildly context-sensitive grammar formalisms. University of Pennsylvania, United States Januar 1988 (englisch, acm.org – Dissertation in Computer and Information Science).