文脈依存言語
ふたつの文脈依存言語に対して和集合、積集合、連結を施した結果も文脈依存言語である。
文脈依存言語の補集合は文脈依存言語である。
文脈自由言語は文脈依存言語に含まれる(ただしその文脈依存文法の定義に S → ε という規則が含まれる場合のみ)。
文脈依存言語(ぶんみゃくいそんげんご、Context-sensitive Language)は、文脈依存文法で定義される形式言語である。これはチョムスキー階層の四つの文法のひとつであるが、理論的にも実用的にも最も使われることが少ない文法でもある。
文脈自由ではない文脈依存言語の例として、L = { a : n は素数 } がある。これを示す簡単な方法は線形拘束オートマトンを使うことである。
他に、L = { abc : n は正の整数 } 等がある。