文脈自由言語のソースを表示

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

* 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> は以下のように定義される。

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

例えば、数式など（[[プログラミング言語]]などにおける）の括弧の対応は <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法]]を参照されたい）

== 参考文献 ==
* {{cite book|author = Michael Sipser | date = 1997年 | title = Introduction to the Theory of Computation | publisher = PWS Publishing | id = ISBN 0-534-94728-X}} Chapter 2: Context-Free Languages, pp.91–122.

{{DEFAULTSORT:ふんみやくしゆうけんこ}}
[[Category:形式言語]]
[[Category:構文解析 (プログラミング)]]
[[Category:数学に関する記事]]