~2025-49283-4 am 31. August 2025 um 15:27 Uhr

2025-08-31T15:27:32Z

Neue Seite

[[Datei:TAG-introductory-example-German-composing-process-and-result.svg|mini|Beispiel-Baumadjunktionsgrammatik bestehend aus drei Elementarbäumen (<math>\alpha_1, \alpha_2, \beta_1</math>). Gezeigt ist zudem, wie diese den Satz ''Rumo schnarcht nie'' erzeugt.]]
'''Tree-adjoining grammar'''s (TAG), auch '''Baumadjunktions-Grammatiken''', sind [[formale Grammatik]]en, die von [[Aravind Joshi]] eingeführt wurden<ref name=":0">{{Literatur |Autor=Aravind K. Joshi, Leon S. Levy, Masako Takahashi |Titel=Tree adjunct grammars |Sammelwerk=Journal of Computer and System Sciences |Band=10 |Nummer=1 |Datum=1975-02 |Sprache=en |DOI=10.1016/S0022-0000(75)80019-5 |Seiten=136-163 |Online=https://www.sciencedirect.com/science/article/pii/S0022000075800195}}</ref> und in der [[Computerlinguistik]] für die Beschreibung von [[Natürliche Sprache|natürlichen Sprachen]] verwendet werden.

TAGs ähneln [[Kontextfreie Grammatik|kontextfreien Grammatiken]], verwenden aber [[Baum (Graphentheorie)|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 Grammatik]]en in der [[Chomsky-Hierarchie]].<ref name=":1">{{Literatur |Autor=David Jeremy Weir |Titel=Characterizing mildly context-sensitive grammar formalisms |Verlag=University of Pennsylvania |Ort=United States |Datum=1988-01 |Sprache=en |Kommentar=Dissertation in Computer and Information Science |Online=https://dl.acm.org/doi/abs/10.5555/914916}}</ref> Daher sind sie vermutlich stark genug, um natürliche Sprachen zu erzeugen, aber auch schwach genug, um noch effizient [[Parser|parsebar]] zu sein.

== Einstiegsbeispiel ==
[[Datei:TAG-introductory-example-German-composing-process-and-result.svg|rahmenlos|746x746px]]

Eine Baumadjunktionsgrammatik, die sowohl den Satz ''Rumo schnarcht'' als auch ''Rumo schnarcht nie'' verarbeiten kann, lässt sich zum Beispiel mit drei Elementarbäumen darstellen:

* ein '''Initalbaum''' <math>\alpha_1</math>für die [[Nominalphrase]] für das Wort ''Rumo''. Der Baum besteht aus dem Symbol NP (einem [[Nichtterminalsymbol]]), welches zu dem Wort ''Rumo'' (einem [[Terminalsymbol]]) expandiert.
* ein '''Initalbaum''' <math>\alpha_2</math> für das Verb ''schnarcht''. Der Baum zeigt an, dass dem Verb zu einem ganzen Satz noch eine Nominalphrase (NP) fehlt. Der Baumknoten NP ist mit <math>\downarrow</math> als ''Substitutionsknoten'' markiert, um zu signalisieren, dass an dieser Stelle noch ein Baum mit einer NP als Wurzel eingesetzt werden muss. Ansonsten besteht der <math>\alpha_2</math>-Baum noch aus einer [[Verbalphrase]] (VP), welche wiederum aber lediglich aus dem Verb ''schnarcht'' besteht.
* ein '''Auxiliarbaum''' <math>\beta_1</math>für das Adverb ''nie''. Der Baum besteht neben dem [[Adverb]] ''nie'' noch aus zwei weiteren VP-Knoten. Jeder Auxiliarbaum besitzt einen speziellen Fußknoten, markiert durch <math>\ast</math>, der das gleiche Nichtterminal wie die Wurzel des Baums aufweisen muss. In diesem Fall ist das eine VP. Dieser Baum kann also dazu genutzt werden, um Verbalphrasen zu modifizieren.

Um den Satz ''Rumo schnarcht'' zu erhalten, müssen nur die zwei Initialbäume <math>\alpha_1</math> und <math>\alpha_2</math> mittels ''Substitution'' miteinander kombiniert werden. Dazu wird der Substitutionsknoten mit der Wurzel des NP-Baums ersetzt. Soll der Satz um das Adverb ''nie'' erweitert werden, kommt die Adjunktion zum Einsatz, die den Baumadjunktionsgrammatiken auch ihren Namen gab. Bei der Adjunktion wird der Baum des bisherigen Satzes am VP-Knoten quasi in zwei Teile gerissen. Der Teilbaum des Satzes oberhalb des ursprünglichen VP-Knotens endet nun in der Wurzel des Auxiliarbaums <math>\beta_1</math>, während der unter Teilbaum nun an dem ehemaligen Fußknoten des Auxiliarbaums beginnt. Theoretisch kann diese Adjunktion beliebig oft wiederholt werden (''Rumo schnarcht nie nie nie nie ...'').

== Definition ==
Eine TAG ist ein 5-[[Tupel]] <math>(\Sigma, NT, I, A, S)</math> bestehend aus<ref name=":4">{{Literatur |Autor=Aravind K. Joshi, Yves Schabes |Titel=Tree-Adjoining Grammars and Lexicalized Grammars |Verlag=University of Pennsylvania Department of Computer and Information Science |Datum=1991-03-01 |Kommentar=Technical Report No. MS-CIS-91-22. |Online=https://repository.upenn.edu/handle/20.500.14332/7375}}</ref>

* <math>\Sigma</math>, einer endlichen Menge von [[Terminalsymbol]]en;
* <math>NT</math>, einer endlichen Menge von [[Nichtterminalsymbol]]en, die mit der Menge der Terminale [[disjunkt]] ist;
* <math>I</math>, einer endlichen Menge von ''Initialbäumen.'' Initialbäume sind solche Bäume, die
** als innere Knoten Nichtterminale besitzen und
** als Blätter Nichtterminale oder Terminale, wobei Nichtterminale mit <math>\downarrow</math> markiert sind, um Substitution anzuzeigen.
* <math>A</math>, einer endlichen Menge an ''Auxiliarbäumen''. Auxiliarbäume sind solche Bäume, die
** als innere Knoten Nichtterminale besitzen und
** als Blätter Nichtterminale oder Terminale, wobei Nichtterminale üblicherweise mit <math>\downarrow</math> markiert werden, um Substitution anzuzeigen. Einer der Nichtterminalblätter ist hingegen nicht zur Substitution bestimmt, sondern ein ''Fußknoten'' (markiert als <math>\ast</math>) mit dem gleichen Nichtterminal wie die Wurzel des Auxiliarbaums.
* <math>S</math>, dem speziellen Startsymbol der TAG, welches ein Nichtterminal ist: <math>S \in NT</math>

Die Menge an Initial- und Auxiliarbäumen <math>I \cup A</math> wird Menge der ''Elementarbäume'' genannt.

Zur Kombination von Bäumen stehen zwei Operationen zur Verfügung: Substitution und Adjunktion:

* ''Substitution'': bei dieser Operation wird ein Nichtterminalblatt eines Baumes durch die Wurzel eines anderen Baumes, der aus Initialbäumen abgeleitet wurde, ersetzt und damit die beiden Bäume verbunden.

[[Datei:TAG-schematic-substitution.svg|alternativtext=Schematische Darstellung der Substitution: Ausgangspunkt sind zwei Bäume. Ein Baum alpha mit Wurzelsymbol Y und einem Blatt-Knoten X markiert zur Substitution. Ein zweiter Baum beta mit einem Blatt mit Nichtterminal X als Wurzel. Ein Pfeil zeigt von der Wurzel von beta auf den X-Knoten von alpha und deutet damit an, wo die Bäume kombiniert werden. Ebenfalls gezeigt ist das Resultat der Substitution: der Baum wurzelt immer noch in Symbol Y wie ursprünglich alpha, allerdings ist am ehemaligen Blatt-Knoten mit Symbol X jetzt der zweite Baum angedockt.|rahmenlos|474x474px]]

* ''Adjunktion'': bei dieser Operation wird ein Auxiliarbaum in einen anderen Baum eingefügt. Dieser zweite Baum muss dafür ein Nichtterminal besitzen, welches der Wurzel und dem Fußknoten des Auxiliarbaums entspricht. Adjunktion an für die Substitution markierten Blättern ist nicht erlaubt. Adjunktion sieht dabei wie folgt aus:

[[Datei:TAG-schematic-adjunction.svg|alternativtext=Schematische Darstellung der Adjunktion: Ausgangspunkt sind zwei Bäume. Ein Baum alpha mit Wurzelsymbol Y und einem inneren Knoten mit Symbol X. Ein zweiter Baum (Auxiliarbaum!) beta mit Wurzelsymbol X und einem Fußknoten mit Symbol X. Ein Pfeil zeigt von der Wurzel von beta auf den inneren X-Knoten von alpha und deutet damit an, wo die Bäume kombiniert werden. Ebenfalls gezeigt ist das Resultat der Adjunktion: der Baum wurzelt immer noch in Symbol Y, allerdings ist am inneren Knoten mit Symbol X jetzt der ehemalige Auxiliarbaum eingefügt und der vormalige X-wurzelnde Teilbaum von alpha ist an dem ehemaligen Fußknoten von beta angedockt. So gibt es jetzt zwei interne Knoten mit dem Symbol X und der Baum ist dadurch tiefer geworden.|rahmenlos|474x474px]]

Daneben gibt es noch die Möglichkeit, ''Adjunktions-Constraints'' für Knoten einzuführen:<ref name=":4" />

* ''Selektive Adjunktion'' (SA(T)): nur eine bestimmte Teilmenge T an Auxiliarbäumen darf an diesem Knoten adjungieren.
* ''Null Adjunktion'' (NA): an einem mit NA markierten Knoten darf nicht adjungiert werden.
* ''Obligatorische Adjunktion'' (OA(T)): an einem mit OA markierten Knoten muss adjungiert werden. Dazu muss ein Auxiliarbaum aus einer bestimmten Teilmenge T verwendet werden.

In der Definition von Joshi et al. (1975)<ref name=":0" /> gab es hingegen noch keine Constraints und Substitutionsknoten.<ref name=":4" />

== Expressivität ==
Obwohl TAGs aus Bäumen bestehen, fokussiert sich dieser Abschnitt auf die String-Sprachen von TAGs. Das sind die Sprachen, die sich an den Blättern der Bäume aus den Terminalsymbolen ablesen lassen.

=== Relation zu kontextfreien Grammatiken ===
Zu jeder [[Kontextfreie Grammatik|kontextfreien Grammatik]] (CFG, für englisch ''context-free grammar'') kann eine TAG erzeugt werden, die die gleiche String-Sprache akzeptiert. Damit können TAGs alle [[Kontextfreie Sprache|kontextfreien Sprachen]] beschreiben.<ref name=":0" />

=== Schwach kontextsensitive Sprachen ===
TAGs können aber mehr Sprachen beschreiben als kontextfreie Grammatiken. Denn mit TAGs können auch einige, aber nicht alle [[Kontextsensitive Sprache|kontextsensitiven Sprachen]] beschrieben werden, wie folgende Beispiele verdeutlichen.[[Datei:Copy-language-tag.jpg|mini|Bäume um die Copy-Sprache mit <math>\Sigma = \left\{ a, b \right\}</math>zu generieren. Das [[Leeres Wort|leere Wort]] ist als <math>\epsilon</math> dargestellt. An den mit Subskript ''na'' annotierten Nichtterminal-Knoten kann nicht adjungiert werden.]]Zu den Beispielen von kontextsensitiven Sprachen, die von TAGs akzeptiert werden können, zählen folgende:

* Die Copy-Sprache <math>\textsf{COPY} = \left\{ ww \mid w \in \Sigma^* \right\}</math> kann von TAGs mit Adjunktionsconstraints ausgedrückt werden.<ref name=":2" /><ref name=":3" /> Wenn das Vokabular <math>\Sigma = \left\{ a, b \right\}</math> ist, reichen nur drei Bäume aus, um die Sprache zu beschreiben. Ein Baum für das [[Leeres Wort|leere Wort]] und je ein weiterer für das Symbol ''a'' und ''b''. Zur Sprache gehören Sätze wie ''abab'' und ''abaaba''.

[[Datei:Anbncndn.jpg|mini|Bäume für die COUNT-4-Sprache. Der Baum links generiert nur das [[Leeres Wort|leere Wort]] (<math>\epsilon</math>).]]

* Die Count-4-Sprache,<ref name=":3">{{Literatur |Autor=Aravind K. Joshi |Titel=Tree adjoining grammars: How much context-sensitivity is required to provide reasonable structural descriptions? |Hrsg=D. Dowty, L. Karttunen, and A. Zwicky |Sammelwerk=Natural Language Parsing |Verlag=Cambridge University Press |Datum=1985 |Sprache=en |Seiten=206-250 |Online=https://www.cs.sfu.ca/~anoop/courses/ReadingGroup-Summer-2006/joshi85.pdf |Abruf=2025-06-23}}</ref> bei der genau gleich viele Symbole ''a'', ''b'', ''c'' und ''d'' generiert werden sollen, kann auch von TAGs mit Adjunktionsconstraints beschrieben werden. Formal ist diese definiert als <math>\textsf{COUNT}_ 4 = \left\{ a^n b^n c^n d^n \mid n \geq 0 \right\}</math> und lässt sich mit nur zwei Bäumen generieren.<ref name=":3" />

Zwei Beispiele für kontextsensitive Sprachen, die TAGs nicht beschreiben können, sind die Count-5-Sprache <math>\textsf{COUNT}_ 5 = \left\{ a^n b^n c^n d^n f^n \mid n \geq 0 \right\}</math> und die doppelte Copy-Sprache <math>\textsf{DOUBLE-COPY} = \left\{ www \mid w \in \Sigma^* \right\}</math>.<ref name=":3" />

TAGs können die gleichen ''schwach kontextsensitiven'' Sprachen von Strings wie zum Beispiel [[Kombinatorische Kategorialgrammatik|kombinatorische Kategorialgrammatiken]] (''Combinatory Categorical Grammars'', CCGs) erzeugen.<ref name=":1" />

=== Parsing ===
TAGs können mit einem [[Cocke-Younger-Kasami-Algorithmus|CYK]]- oder [[Earley-Algorithmus|Early]]-ähnlichen<ref name=":2">{{Literatur |Autor=K. Vijay-Shankar, Aravind K. Joshi |Titel=Some Computational Properties of Tree Adjoining Grammars |Sammelwerk=Strategic Computing - Natural Language Workshop: Proceedings of a Workshop Held at Marina del Rey, California, May 1-2, 1986 |Datum=1986-05 |Sprache=en |Seiten=212-223 |Online=https://aclanthology.org/H86-1020.pdf}}</ref><ref>{{Literatur |Autor=Yves Schabes, Aravind K. Joshi |Titel=An Earley-Type Parsing Algorithm for Tree Adjoining Grammars |Sammelwerk=6th Annual Meeting of the Association for Computational Linguistics |Verlag=Association for Computational Linguistics |Ort=Buffalo, New York, USA |Datum=1988-06 |Sprache=en |DOI=10.3115/982023.982055 |Seiten=258–269 |Online=https://aclanthology.org/P88-1032.pdf}}</ref> Parsing-Algorithmus geparst werden. Sie sind daher noch in polynomieller Zeit, genauer in <math>\mathcal{O}\left( n^6 \right)</math>, parsebar (siehe [[Landau-Notation]]).<ref name=":4" />

== Varianten und Erweiterungen ==

* '''Lexikalisierte TAG (LTAG):''' bei einer LTAG enthält jeder Elementarbaum mindestens ein Terminalsymbol, welches auch (lexikalischer) Anker genannt wird.<ref name=":4" />
* '''Feature-TAG (FTAG):''' Bäume werden mit Merkmalsstrukturen annotiert, um [[Kongruenz (Grammatik)|Kongruenz]] zu erzwingen, zum Beispiel zwischen einem Verb im [[Singular]] und dem Subjekt, das auch im Singular sein soll.<ref>{{Literatur |Autor=K. Vijay-Shanker, A.K. Joshi |Titel=Feature Structures Based Tree Adjoining Grammars |Sammelwerk=Coling Budapest 1988 Volume 2: International Conference on Computational Linguistics |Datum=1988 |Sprache=en |Online=https://aclanthology.org/C88-2147/ |Abruf=2025-06-26}}</ref>

== Siehe auch ==

* [[Kontextfreie Grammatik]]
* [[Kontextsensitive Grammatik]]
* [[Chomsky-Hierarchie]]
* [[Syntaxtheorie]]

== Literatur ==

* {{Literatur |Autor=Stefan Müller |Titel=Grammatiktheorie |Sammelwerk=Stauffenburg Einführungen |Band=20 |Verlag=Stauffenberg Verlag |Ort=Tübingen |Datum=2010 |Sprache=de |ISBN=978-3-86057-805-6 |Online=https://hpsg.hu-berlin.de/~stefan/Pub/grammatiktheorie.pdf}}, insbesondere [https://hpsg.hu-berlin.de/~stefan/Pub/grammatiktheorie.pdf#chapter.10 Kapitel 10] zu TAG.
* {{Literatur |Autor=Aravind K. Joshi, Leon S. Levy, Masako Takahashi |Titel=Tree adjunct grammars |Sammelwerk=Journal of Computer and System Sciences |Band=10 |Nummer=1 |Datum=1975-02 |Sprache=en |DOI=10.1016/S0022-0000(75)80019-5 |Seiten=136-163 |Online=https://www.sciencedirect.com/science/article/pii/S0022000075800195}}
* {{Literatur |Autor=Laura Kallmeyer |Titel=Parsing Beyond Context-Free Grammars |Band= |Verlag=Springer Berlin Heidelberg |Ort=Berlin, Heidelberg |Datum=2010 |Sprache=en |Reihe=Cognitive Technologies |ISBN=978-3-642-14845-3 |DOI=10.1007/978-3-642-14846-0 |Kommentar=Kapitel zu TAG auf Seiten 53 - 108 |Online=https://link.springer.com/10.1007/978-3-642-14846-0 |Abruf=2025-06-23}}
* {{Literatur |Autor=Aravind K. Joshi, Yves Shabes |Titel=Tree-Adjoining Grammars |Hrsg=Grzegorz Rozenberg, Arto Salomaa |Sammelwerk=Handbook of Formal Languages |Verlag=Springer |Ort=Berlin, Heidelberg |Datum=1997 |ISBN=978-3-642-59126-6 |DOI=10.1007/978-3-642-59126-6_2}}

== Weblinks ==
* [https://www.cis.upenn.edu/~xtag/ XTAG project], verwendet eine TAG für natürliche Sprache
* [https://user.phil-fak.uni-duesseldorf.de/~kallmeyer/TAG/ Seminar zu TAG] von Laura Kallmeyer und Simon Petitjean für das Wintersemester 2015/16 mit Foliensätzen zu verschiedenen Bereichen von TAGs.

== Einzelnachweise ==

<references />
[[Kategorie:Computerlinguistik]]
[[Kategorie:Grammatiktheorie]]

Tree Adjoining Grammar - Versionsgeschichte

~2025-49283-4 am 31. August 2025 um 15:27 Uhr