木接合文法のソースを表示

'''木接合文法'''（[[英語|英]]: '''Tree-Adjoining Grammar'''、'''TAG'''）とは、{{仮リンク|アラビンド・ジョシ|en|Aravind Joshi}} らによる、[[形式文法]]の一種である。[[文脈自由文法]]にいくぶん似ているが、シンボルの書き換えではなく、[[木 (数学)|木]]の書き換えをベースとすることが特徴で、文脈自由文法は、シンボルの書き換えのための生成規則群から成るが、木のノード群を書き換える規則群から成る（[[木 (数学)|木]]および[[木構造 (データ構造)|木構造]]参照）。

== 概要 ==
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 | date = 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 | first2=Owen |last2=Rambow | title = A Formalism for Dependency Grammar Based on Tree Adjoining Grammar | date = 2003年 | book-title = Proceedings of the Conference on Meaning-Text Theory | url = http://www1.cs.columbia.edu/~rambow/papers/joshi-rambow-2003.pdf}}</ref>。補助木の根ノードと foot node のラベルは、挿入箇所のノードのラベルと一致していなければならない。

== 複雑性と応用 ==
=== 言語とオートマトンの理論 ===
木接合文法は、文脈自由文法よりも強力だが[[文脈依存文法]]よりも弱い。

具体例として、任意の文字列を二回繰り返すような言語を記述することができる。より一般には、 <math>\{a^n b^n c^n d^n | 1 \le n \}</math> のような文脈自由文法に含まれない言語を記述することができる。このような処理は[[:en:embedded pushdown automaton|embedded pushdown automaton]]で表現できる。一方で、文字列を3回繰り返す言語や、5つ以上の文字をそれぞれ同じ長さで順に並べた列からなる言語は木接合文法では生成できない。

木接合文法は[[弱文脈依存言語|弱文脈依存]]文法の1つであり、よって[[チョムスキー階層]]には当てはまらないが、その関連性はよく研究されている<ref name="Joshi1969">{{cite paper | last = Joshi | first = Aravind | title = Properties of Formal Grammars with Mixed Types of Rules and Their Linguistic Relevance | date = 1969年 | publisher = Proceedings Third International Symposium on Computational Linguistics, Stockholm, Sweden }}</ref>。

=== 自然言語 ===
前節で述べたような性質から、[[計算言語学]]や[[自然言語処理]]でよく使われる。また、[[構文解析]]が一般に効率的に行えるなら、[[自然言語]]のモデルとして十分に意味があるという主張もある<ref name="joshi1985">{{cite book | last = Joshi | first = Aravind | chapter = How much context-sensitivity is necessary for characterizing structural descriptions | date = 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>。

== 歴史 ==
TAGの研究は、[[ゼリグ・ハリス]]の文字列文法である adjunction grammars (AG) <ref name="JoshiKosarajuYamada1969">{{cite paper | last = Joshi | first = Aravind | coauthors =  S. R. Kosaraju, H. Yamada | title = String Adjunct Grammars | date = 1969年 | publisher = Proceedings Tenth Annual Symposium on Automata Theory, Waterloo, Canada }}</ref>を Joshi らが研究したことから端を発している。AG は、自然言語学的な観点からは、内心構造（endocentric construction）を自然かつ効率的に扱えるが、外心構造（exocentric construction）はうまく扱えない。[[句構造文法]]はその逆である。1969年、Joshi は2種類の規則群を混合することで、少数の非常に単純な書き換え規則で、付加規則のための文字列の語彙を生成する、この相補性を同時に扱えるTAGを生み出した。

== 脚注 ==
{{Reflist}}

== 外部リンク ==
*[http://www.cis.upenn.edu/~xtag/ The XTAG project] 自然言語処理へのTAGの応用
*[http://www.let.rug.nl/~vannoord/papers/diss/diss/node59.html A tutorial on TAG]
*[http://wiki.loria.fr/wiki/SemConst/Documentation#Background SemConst Documentation] TAGフレームワークでの統語論と意味論のインタフェース問題の概説

{{DEFAULTSORT:きせつこうふんほう}}
[[Category:生成文法]]
[[Category:文法フレームワーク]]