文脈自由言語

出典: フリー百科事典『ウィキペディア（Wikipedia）』
移動先: 案内、 検索

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

  • 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 を正規言語としたとき、以下も全て文脈自由言語である（閉じている）。

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

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

文脈自由言語は積集合において閉じていない。この証明は参考文献にある 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法を参照されたい）

参考文献

「http://wikippe.e-do-match.com/index.php?title=文脈自由言語&oldid=27」から取得