「弱文脈依存言語」の版間の差分

特徴
(まずは概要を)
 
(特徴)
'''弱文脈依存文法''' (Mildly Context-sensitive Grammars) とは、 Joshi (1985) の提案した[[自然言語]]の理論に必要であろう性質特徴を持った[[形式文法]]の概念総称で、そのような[[文法]]によって定義づけられる言語クラスが'''弱文脈依存言語''' (Mildly Context-sensitive Languages) である。
 
[[チョムスキー階層]]の[[文脈依存言語]]の中でも[[文脈自由言語]]に一番近い部分にあたり、[[Indexed Languages]] (IL) ほどは生成力がない。Joshi の[[木接合文法]] (TAG) の研究の中から生まれた概念だが、TAG以外にもこのクラスの言語を定義するいろいろな文法が[[言語学]]および形式言語論において提案されている。また、形式言語・オートマトン的な研究も進んでおり、Weir (1992) によって弱文脈依存言語の性質を持つ言語の階層 (Weir's Control Language Hierarchy) が対応するオートマトンとともに定義づけられている。
 
 
== 特徴 ==
 
Joshi (1985) は以下の特徴を弱文脈依存文法を定義づけるものとしてあげている:
# 弱文脈依存言語は文脈自由言語を正当に包含する。
# 弱文脈依存の言語は多項式時間で認識可能である。
# 弱文脈依存文法は特定の依存関係、入れ子状と限られた種類の交差、のみを捉える事が出来る。
# 弱文脈依存の言語は定数的増加 (constant growth) 特性を持つ。
弱文脈依存言語の研究の背景には、自然言語が文脈自由言語の性質を多く持つにも関わらず、弱生成力が文脈自由文法を超えるケースがある事がある。上記の下3点はその文脈自由の持つ性質を一般化したものとも言える。
 
== Reference ==
[[Category:理論計算機科学]]
 
[[en:Mildly Contextcontext-sensitive Languageslanguage]]
309

回編集