文脈依存文法
文脈依存文法（ぶんみゃくいぞんぶんぽう、Context-sensitive Grammar）は、形式文法 G = (N, Σ, P, S) において P の生成規則が以下のような形式のものをいう。
- αAβ → αγβ
ここで A は N に属する非終端記号であり、α と β は (N ∪ Σ)* である（すなわち α と β は非終端記号と終端文字から構成される文字列である）。また、γ は (N ∪ Σ)+ である（すなわち γ は空でない非終端記号と終端文字で構成される文字列である）。さらに、以下のような生成規則が存在することもある。
- S → ε
ここで、ε は空の文字列である。ただしこのとき、S が生成規則の右側に出現してはならない。この規則を許すことで、空文字列を含む文脈依存言語の定義が可能になり、文脈依存言語が文脈自由言語を真に含むと言えるようになる。
概要
「文脈依存」という用語は、Aの前後の α と β を意味している。つまり A の前後の文脈によって A を γ に置換できるかどうかを判断しているからである。これは文脈自由文法と異なる点であり、文脈自由文法では終端文字列の文脈（つまり非終端記号の前後の終端文字列）は生成規則上無視される。文脈依存文法で記述される形式言語は文脈依存言語と呼ばれる。
文脈依存文法の概念は1950年代にノーム・チョムスキーによって導入されたもので、文脈によってある単語がその位置に存在することが適当か否かが判断される自然言語の文法を記述する方法として考案されたものである。
もうひとつの定義
文脈依存文法の別の定義として、P 内の生成規則に次のような制限を与えたものがある。各生成規則は α -> β という形式で、| α | ≤ | β | という制限に従う。ここで | α | は α の長さである。この文法では生成規則を適用したときに文字列の長さが減ることがないので、「単調文法」（Monotonic Grammar）とか「非縮小文法」（Noncontracting Grammar）などと呼ばれる。
非縮小文法と文脈依存文法は異なるが、同じ言語クラスを定義できるという意味でほぼ等価である（違いは、非縮小文法では空の文字列 ε を含む言語を生成できない点である）。文脈依存文法で記述された言語 L に対して、非縮小文法は L - {ε} を記述できるし、その逆も真である。
例
文脈依存文法の例を以下に示す。
- S → aSBC | aBC
- CB → HB
- HB → HC
- HC → BC
- aB → ab
- bB → bb
- bC → bc
- cC → cc
ここで、| は同じ非終端記号からの生成規則を列挙する代わりに一行で表記するために用いられている。この文法が生成する言語は [math] \{ a^n b^n c^n : n \ge 1 \} [/math] であり、これは文脈自由言語ではない。文脈依存文法では生成規則を適用する際に複数の文字（文字列）に対してパターンマッチさせるようになっており、マッチすべき文字数に制限はない。一方で文脈自由文法ではパターンマッチするのは常に一文字（非終端記号）である。文脈依存文法で記述できる言語として [math] \{ a^n b^n c^n d^n : n \ge 1 \} [/math] というものもあるが、これの生成規則は上記のものより更に複雑になる。
この文法で「aaabbbccc」をマッチさせるときの流れは、以下のようになる。
- S
- → aSBC
- → aaSBCBC
- → aaaBCBCBC
- → aaaBHBCBC
- → aaaBHCCBC
- → aaaBBCCBC
- → aaaBBCHBC
- → aaaBBCHCC
- → aaaBBCBCC
- → aaaBBHBCC
- → aaaBBHCCC
- → aaaBBBCCC
- → aaabBBCCC
- → aaabbBCCC
- → aaabbbCCC
- → aaabbbcCC
- → aaabbbccC
- → aaabbbccc
上の例を等価な単調文法で書くと、以下のようになる。
- S → abc | aSBc
- cB → Bc
- bB → bb
標準形
空の文字列を生成しない文脈依存文法は、等価な黒田標準形に変換可能である。ここでいう「等価」というのは同じ言語を生成する文法を記述できるという意味である。
計算属性
ある文字列 s が文脈依存文法 G で記述される言語に属するか否かという決定問題は、PSPACE完全である。実際、文脈依存文法の中にはその文法認識問題がPSPACE完全なものもある。