文脈自由言語

文脈自由言語（ぶんみゃくじゆうげんご）とは、次のような再帰的な生成規則をもつ文脈自由文法によって、与えられた言語の長さ n に対して O(n³) の時間で認識される形式言語。プッシュダウン・オートマトンで受理可能な言語と等価である。

• S → E.
• E → T | E - T | E + T | (E).
• T → T * E | T / E | id | num.

ある言語が文脈自由言語でないことを証明するために文脈自由言語の反復補題が使われることがある。

例

基本的な文脈自由言語 [math]L = \{a^nb^n:n\geq1\}[/math] は、偶数個の文字から成る文字列で構成され、各文字列の前半は a で、後半は b で構成される。L を生成する文法は [math]S\to aSb ~|~ ab[/math] であり、プッシュダウン・オートマトン [math]M=(\{q_0,q_1,q_f\}, \{a,b\}, \{a,z\}, \delta, q_0, \{q_f\})[/math] に受容される。ここで [math]\delta[/math] は以下のように定義される。

[math]\delta(q_0, a, z) = (q_0, a)[/math]
[math]\delta(q_0, a, a) = (q_0, a)[/math]
[math]\delta(q_0, b, a) = (q_1, x)[/math]
[math]\delta(q_1, b, a) = (q_1, x)[/math]
[math]\delta(q_1, b, z) = (q_f, z)[/math]
ここで z は初期スタック記号、x はポップ動作を意味する。

例えば、数式など（プログラミング言語などにおける）の括弧の対応は [math]S\to SS ~|~ (S) ~|~ \lambda[/math] というような規則になる。数式などはだいたい文脈自由言語である。

閉包属性

L と P を文脈自由言語、D を正規言語としたとき、以下も全て文脈自由言語である（閉じている）。

• L のクリーネ閉包 [math]L^*[/math]
• L の準同型 φ(L)
• L と P の連結 [math]L \circ P[/math]
• L と P の和集合 [math]L \cup P[/math]
• L と（正規言語） D の積集合 [math]L \cap D[/math]

しかし、積集合や差集合に関しては閉じていない。これらの操作の具体的な内容については形式言語の情報工学的定義を参照されたい。

積集合操作で閉じていないことの証明

文脈自由言語は積集合において閉じていない。この証明は参考文献にある Sipser 97 の練習問題となっている。まず、2つの文脈自由言語 [math]A = \{a^m b^n c^n \mid m, n \geq 0 \}[/math] と [math]B = \{a^n b^n c^m \mid m,n \geq 0\}[/math] を用意する。これらの積集合 [math]A \cap B = \{ a^n b^n c^n \mid n \geq 0\}[/math] に対して文脈自由言語の反復補題を用いることで、それが文脈自由言語でないことを示すことができる。

決定性属性

文脈自由言語についての以下の問題は決定不能である。

• 等価性: 2つの文脈自由文法 A と B が与えられたとき、[math]L(A)=L(B)[/math] か?
• [math]L(A) \cap L(B) = \emptyset [/math] か?
• [math]L(A)=\Sigma^*[/math] か?
• [math]L(A) \subseteq L(B)[/math] か?

文脈自由言語についての以下の問題は決定可能である。

• [math]L(A)=\emptyset[/math] か?
• L(A) は有限か?
• メンバーシップ: ある単語 w を与えたとき [math]w \in L(A)[/math] か?（メンバーシップ問題は多項式時間で決定可能である。CYK法を参照されたい）

参考文献

• Michael Sipser (1997年). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X.  Chapter 2: Context-Free Languages, pp.91–122.