文脈依存文法とは？わかりやすく解説

文脈依存文法（ぶんみゃくいぞんぶんぽう、英: 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 - {ε} を記述できるし、その逆も真である。