文脈自由言語

文脈自由言語（ぶんみゃくじゆうげんご）とは、次のような再帰的な生成規則をもつ文脈自由文法によって、与えられた言語の長さ n に対して O(n3) の時間で認識される形式言語。プッシュダウン・オートマトンで受理可能な言語と等価である。
ある言語が文脈自由言語でないことを証明するために文脈自由言語の反復補題が使われることがある。
例.
基本的な文脈自由言語 formula_1 は、偶数個の文字から成る文字列で構成され、各文字列の前半は "a" で、後半は "b" で構成される。"L" を生成する文法は formula_2 であり、プッシュダウン・オートマトン formula_3 に受容される。ここで formula_4 は以下のように定義される。
formula_5<br>
formula_6<br>
formula_7<br>
formula_8<br>
formula_9<br>
ここで z は初期スタック記号、x はポップ動作を意味する。
例えば、数式など（プログラミング言語などにおける）の括弧の対応は formula_10 というような規則になる。数式などはだいたい文脈自由言語である。
閉包属性.
"L" と "P" を文脈自由言語、"D" を正規言語としたとき、以下も全て文脈自由言語である（閉じている）。
しかし、積集合や差集合に関しては閉じていない。これらの操作の具体的な内容については形式言語の情報工学的定義を参照されたい。
積集合操作で閉じていないことの証明.
文脈自由言語は積集合において閉じていない。この証明は参考文献にある Sipser 97 の練習問題となっている。まず、2つの文脈自由言語 formula_15 と formula_16 を用意する。これらの積集合 formula_17 に対して文脈自由言語の反復補題を用いることで、それが文脈自由言語でないことを示すことができる。
決定性属性.
文脈自由言語についての以下の問題は決定不能である。
文脈自由言語についての以下の問題は決定可能である。