文脈依存文法のソースを表示

'''文脈依存文法'''（ぶんみゃくいぞんぶんぽう、{{lang-en-short|context-sensitive grammar}}）は、[[形式文法]] ''G'' = (''N'', &Sigma;, ''P'', ''S'') において ''P'' の生成規則が以下のような形式のものをいう。
: &alpha;''A''&beta; &rarr; &alpha;&gamma;&beta;
ここで ''A'' は ''N'' に属する[[非終端記号]]であり、&alpha; と &beta; は (''N'' &cup; &Sigma;)* である（すなわち &alpha; と &beta; は非終端記号と[[終端記号|終端文字]]から構成される文字列である）。また、&gamma; は (''N'' &cup; &Sigma;)<sup>+</sup> である（すなわち &gamma; は空でない非終端記号と終端文字で構成される文字列である）。さらに、以下のような生成規則が存在することもある。
: S &rarr; &epsilon;
ここで、&epsilon; は空の文字列である。ただしこのとき、S が生成規則の右側に出現してはならない。この規則を許すことで、空文字列を含む[[文脈依存言語]]の定義が可能になり、文脈依存言語が[[文脈自由言語]]を真に含むと言えるようになる。

== 概要 ==
「文脈依存」という用語は、''A''の前後の &alpha; と &beta; を意味している。つまり ''A'' の前後の[[文脈]]によって ''A'' を &gamma; に置換できるかどうかを判断しているからである。これは[[文脈自由文法]]と異なる点であり、文脈自由文法では終端文字列の文脈（つまり非終端記号の前後の終端文字列）は生成規則上無視される。文脈依存文法で記述される[[形式言語]]は[[文脈依存言語]]と呼ばれる。

文脈依存文法の概念は[[1950年代]]に[[ノーム・チョムスキー]]によって導入されたもので、文脈によってある単語がその位置に存在することが適当か否かが判断される自然言語の文法を記述する方法として考案されたものである。

== もうひとつの定義 ==
文脈依存文法の別の定義として、''P'' 内の生成規則に次のような制限を与えたものがある。各生成規則は &alpha;&nbsp;->&nbsp;&beta; という形式で、|&nbsp;&alpha;&nbsp;|&nbsp;&le;&nbsp;|&nbsp;&beta;&nbsp;| という制限に従う。ここで |&nbsp;&alpha;&nbsp;| は &alpha; の長さである。この文法では生成規則を適用したときに文字列の長さが減ることがないので、「単調文法」（{{lang-en-short|monotonic grammar}}）とか「非縮小文法」（{{lang-en-short|noncontracting grammar}}）などと呼ばれる。

非縮小文法と文脈依存文法は異なるが、ほぼ{{仮リンク|等価性 (形式言語)|en|Equivalence (formal languages)|label=弱等価}}（同じ言語クラスを定義できる）である。違いは、非縮小文法では空の文字列 &epsilon; を含む言語を生成できない点である。文脈依存文法で記述された言語 ''L'' に対して、非縮小文法は ''L''&nbsp;-&nbsp;{&epsilon;} を記述できるし、その逆も真である。

== 例 ==
文脈依存文法の例を以下に示す。
:S &rarr; aSBC | aBC
:CB &rarr; HB
:HB &rarr; HC
:HC &rarr; BC
:aB &rarr; ab
:bB &rarr; bb
:bC &rarr; bc
:cC &rarr; 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
:&rarr; aSBC
:&rarr; aaSBCBC
:&rarr; aaaBCBCBC
:&rarr; aaaBHBCBC
:&rarr; aaaBHCCBC
:&rarr; aaaBBCCBC
:&rarr; aaaBBCHBC
:&rarr; aaaBBCHCC
:&rarr; aaaBBCBCC
:&rarr; aaaBBHBCC
:&rarr; aaaBBHCCC
:&rarr; aaaBBBCCC
:&rarr; aaabBBCCC
:&rarr; aaabbBCCC
:&rarr; aaabbbCCC
:&rarr; aaabbbcCC
:&rarr; aaabbbccC
:&rarr; aaabbbccc

上の例を弱等価な単調文法で書くと、以下のようになる。
:S &rarr; abc | aSBc
:cB &rarr; Bc
:bB &rarr; bb

== 標準形 ==
空の文字列を生成しない文脈依存文法は、弱等価な[[黒田標準形]]に変換可能である。

== 計算属性 ==
ある文字列 ''s'' が文脈依存文法 ''G'' で記述される言語に属するか否かという[[決定問題]]は、[[PSPACE完全]]である。実際、文脈依存文法の中にはその文法認識問題がPSPACE完全なものもある。

== 関連項目 ==
* [[文脈自由文法]]
* [[チョムスキー階層]]
* [[形式言語の階層]]
* [[形式文法]]
* [[句構造規則]]

{{DEFAULTSORT:ふんみやくいそんふんほう}}
[[Category:形式言語]]
[[Category:数学に関する記事]]
[[Category:文法フレームワーク]]