文脈依存言語

文脈依存言語（ぶんみゃくいそんげんご、）は、文脈依存文法で定義される形式言語である。これはチョムスキー階層の四つの文法のひとつであるが、理論的にも実用的にも最も使われることが少ない文法でもある。

 計算属性 
計算性という観点では、文脈依存言語は線形拘束オートマトン（線形拘束された非決定性チューリングマシン）と等価である。これは、テープ長が kn セルに制限された非決定性チューリングマシンである。ここで n は入力の長さ、k はそのマシンに対応した定数である（つまりテープ長は入力の長さに比例する）。要するに、そのようなマシンで判定できる形式言語は文脈依存言語であり、文脈依存言語はそのようなマシンで判定できる。

このクラスの言語の集合は非決定性チューリングマシンの線形空間に受容されるのでNLIN-SPACE（Non-deterministic Linear Space）として知られている。同様に決定性チューリングマシンに受容される言語については LIN-SPACE と呼ぶ。LIN-SPACE は NLIN-SPACE の部分集合であることは明らかである。LIN-SPACE = NLIN-SPACE であるかどうかは不明であるが、一般に等価ではないと考えられている。

 例 
文脈自由ではない文脈依存言語の例として、L = { an : n は素数 } がある。これを示す簡単な方法は線形拘束オートマトンを使うことである。

他に、L = { anbncn : n は正の整数 } などがある。

 文脈依存言語の属性 
 ふたつの文脈依存言語に対して和集合、積集合、連結を施した結果も文脈依存言語である。
 文脈依存言語の補集合は文脈依存言語である。
 文脈自由言語は文脈依存言語に含まれる（ただしその文脈依存文法の定義に S → ε という規則が含まれる場合のみ）。

 関連項目 
チョムスキー階層
弱文脈依存言語

Category:形式言語
Category:数学に関する記事