「木接合文法」の版間の差分

TAGの研究は、[[ゼリグ・ハリス]]の文字列文法である adjunction grammars (AG) <ref name="JoshiKosarajuYamada1969">{{cite paper | last = Joshi | first = Aravind | coauthors = S. R. Kosaraju, H. Yamada | title = String Adjunct Grammars | yeardate = 1969年 | publisher = Proceedings Tenth Annual Symposium on Automata Theory, Waterloo, Canada }}</ref>を Joshi らが研究したことから端を発している。AG は言語の内心的属性を自然かつ効率的に扱えるが、外心的構造はうまく扱えない。[[チョムスキー階層|句構造文法]]はその逆である。1969年、Joshi は2種類の規則群を混合することで、この相補性を同時に扱える文法を生み出した。少数の非常に単純な書き換え規則で、付加規則のための文字列の語彙を生成する。これは、[[チョムスキー階層]]には当てはまらず、むしろ言語学的に興味深い形でそれと交差している<ref name="Joshi1969">{{cite paper | last = Joshi | first = Aravind | title = Properties of Formal Grammars with Mixed Types of Rules and Their Linguistic Relevance | yeardate = 1969年 | publisher = Proceedings Third International Symposium on Computational Linguistics, Stockholm, Sweden }}</ref>。

TAGにおける規則は、''foot node'' と呼ばれる特殊な葉ノードを持つ木であり、foot node には単語が付属している。TAGにおける木は2種類に分類される。''initial''（初期）木（'<math>\alpha</math>' とも）と ''auxiliary''（補助）木（'<math>\beta</math>'）である。初期木は基本的な結合価的関係を表し、補助木は再帰を許容する<ref name="jurafsky-martin2000">{{cite book | last = Jurafsky | first = Daniel | coauthors = James H. Martin | title = Speech and Language Processing | yeardate = 2000年 | pages = 354 | publisher = Prentice Hall | location = Upper Saddle River, NJ }}</ref>。補助木には根ノードがあり、foot node は初期木と同じシンボルがラベルとして付けられている。導出は、初期木に対して行われ、「置換(substitution)」か「付加(adjunction)」を行っていく。置換とは、先端ノードを、根ノードが同じシンボルのラベルになっている別の木と置換する操作である。付加とは、補助木を別の木の途中に挿入する操作である<ref name="joshi-rambow2003">{{cite conference | last = Joshi | first = Aravind | coauthors = Owen Rambow | title = A Formalism for Dependency Grammar Based on Tree Adjoining Grammar | yeardate = 2003年 | booktitle = Proceedings of the Conference on Meaning-Text Theory | url = http://www1.cs.columbia.edu/~rambow/papers/joshi-rambow-2003.pdf}}</ref>。補助木の根ノードと foot node のラベルは、挿入箇所のノードのラベルと一致していなければならない。

木接合文法は、文脈自由文法よりも強力だが[[文脈依存文法]]よりも弱いという意味で、[[弱文脈依存言語|弱文脈依存]]文法的であると言われることが多い。従って、[[構文解析]]が一般に効率的に行えるなら、[[自然言語]]のモデルとして十分に意味がある<ref name="joshi1985">{{cite book | last = Joshi | first = Aravind | chapter = How much context-sensitivity is necessary for characterizing structural descriptions | yeardate = 1985年 | publisher = Cambridge University Press | pages = 206–250 | title = Natural Language Processing: Theoretical, Computational, and Psychological Perspectives | editor = D. Dowty, L. Karttunen, and A. Zwicky, (eds.) | location = New York, NY }}</ref>。