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

m
弱文脈依存
(en:Tree-adjoining grammar(2007年11月21日 14:49:08(UTC))の翻訳)
 
m (弱文脈依存)
 
== 複雑性と応用 ==
木接合文法は、文脈自由文法よりも強力だが[[文脈依存文法]]よりも弱いという意味で、[[文脈依存言語|弱脈依存]]文法的であると言われることが多い。従って、[[構文解析]]が一般に効率的に行えるなら、[[自然言語]]のモデルとして十分に意味がある<ref name="joshi1985">{{cite book | last = Joshi | first = Aravind | chapter = How much context-sensitivity is necessary for characterizing structural descriptions | year = 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 は[[計算言語学]]や[[自然言語処理]]でよく使われる。
 
TAG は、任意の文字列を二回繰り返すような言語や <math>\{a^n b^n c^n d^n | 1 \le n \}</math> のような言語を記述できる。このような処理は[[:en:embedded pushdown automaton|embedded pushdown automaton]]で表現できる。また、文字列を3回繰り返す言語や、4つ以上の同じ長さの文字の列からなる言語は木接合文法では生成できない。以上から、木接合文法が生成する言語は、弱[[文脈依存言語]]的であるとされる。
 
== 脚注 ==
309

回編集