文脈依存文法
文脈依存文法(ぶんみゃくいぞんぶんぽう、英: context-sensitive grammar)は、形式文法 G = (N, Σ, P, S) において P の生成規則が以下のような形式のものをいう。
αAβ → αγβ
ここで A は N に属する非終端記号であり、α と β は (N ∪ Σ)* である(すなわち α と β は非終端記号と終端文字から構成される文字列である)。また、γ は (N ∪ Σ) である(すなわち γ は空でない非終端記号と終端文字で構成される文字列である)。さらに、以下のような生成規則が存在することもある。
S → ε
ここで、ε は空の文字列である。ただしこのとき、S が生成規則の右側に出現してはならない。この規則を許すことで、空文字列を含む文脈依存言語の定義が可能になり、文脈依存言語が文脈自由言語を真に含むと言えるようになる。