らによる、形式文法の一種である。文脈自由文法にいくぶん似ているが、シンボルの書き換えではなく、木の書き換えをベースとすることが特徴で、文脈自由文法は、シンボルの書き換えのための生成規則群から成るが、木のノード群を書き換える規則群から成る(木および木構造参照)。TAGにおける木は2種類に分類される。初期木は基本的な結合価的関係を表し、補助木は再帰を許容する[1]。初期木と同じシンボルがラベルとして付けられている。導出は、初期木に対して行われ、「置換(substitution)」か「付加(adjunction)」を行っていく。置換とは、先端ノードを、根ノードが同じシンボルのラベルになっている別の木と置換する操作である。付加とは、補助木を別の木の途中に挿入する操作である[2]。ラベルは、挿入箇所のノードのラベルと一致していなければならない。複雑性と応用[編集]言語とオートマトンの理論[編集]木接合文法は、文脈自由文法よりも強力だが文脈依存文法よりも弱い。具体例として、任意の文字列を二回繰り返すような言語を記述することができる。ような文脈自由文法に含まれない言語を記述することができる。automatonで表現できる。一方で、文字列を3回繰り返す言語や、5つ以上の文字をそれぞれ同じ長さで順に並べた列からなる言語は木接合文法では生成できない。木接合文法は弱文脈依存文法の1つであり、よってチョムスキー階層には当てはまらないが、その関連性はよく研究されている[3]。自然言語[編集]前節で述べたような性質から、計算言語学や自然言語処理でよく使われる。構文解析が一般に効率的に行えるなら、自然言語のモデルとして十分に意味があるという主張もある[4]。らが研究したことから端を発している。construction)はうまく扱えない。句構造文法はその逆である。2種類の規則群を混合することで、少数の非常に単純な書き換え規則で、付加規則のための文字列の語彙を生成する、この相補性を同時に扱えるTAGを生み出した。(日時は個人設定で未設定ならばUTC)。表示-継承ライセンスの下で利用可能です。追加の条件が適用される場合があります。詳細は利用規約を参照してください。Cookieに関する声明モバイルビュ。