About: 文脈依存文法

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