(context-free language から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/03/10 07:44 UTC 版)
文脈自由言語 （ぶんみゃくじゆうげんご）とは、次のような再帰的 な生成規則をもつ文脈自由文法 によって、与えられた言語の長さ n に対して O(n3 ) の時間で認識される形式言語 。プッシュダウン・オートマトン で受理可能な言語と等価である。
S → E.
E → T | E - T | E + T | (E).
T → T * E | T / E | id | num.
ある言語が文脈自由言語でないことを証明するために文脈自由言語の反復補題 が使われることがある。
例 基本的な文脈自由言語
L
=
{
a
n
b
n
:
n
≥
1
}
{\displaystyle L=\{a^{n}b^{n}:n\geq 1\}}
a で、後半は b で構成される。L を生成する文法は
S
→
a
S
b
|
a
b
{\displaystyle S\to aSb~|~ab}
M
=
(
{
q
0
,
q
1
,
q
f
}
,
{
a
,
b
}
,
{
a
,
z
}
,
δ
,
q
0
,
{
q
f
}
)
{\displaystyle M=(\{q_{0},q_{1},q_{f}\},\{a,b\},\{a,z\},\delta ,q_{0},\{q_{f}\})}
δ
{\displaystyle \delta }
δ
(
q
0
,
a
,
z
)
=
(
q
0
,
a
)
{\displaystyle \delta (q_{0},a,z)=(q_{0},a)}
δ
(
q
0
,
a
,
a
)
=
(
q
0
,
a
)
{\displaystyle \delta (q_{0},a,a)=(q_{0},a)}
δ
(
q
0
,
b
,
a
)
=
(
q
1
,
x
)
{\displaystyle \delta (q_{0},b,a)=(q_{1},x)}
δ
(
q
1
,
b
,
a
)
=
(
q
1
,
x
)
{\displaystyle \delta (q_{1},b,a)=(q_{1},x)}
δ
(
q
1
,
b
,
z
)
=
(
q
f
,
z
)
{\displaystyle \delta (q_{1},b,z)=(q_{f},z)}
例えば、数式など（プログラミング言語 などにおける）の括弧の対応は
S
→
S
S
|
(
S
)
|
λ
{\displaystyle S\to SS~|~(S)~|~\lambda }
閉包属性 L と P を文脈自由言語、D を正規言語 としたとき、以下も全て文脈自由言語である（閉じている ）。
L のクリーネ閉包
L
∗
{\displaystyle L^{*}}
L の準同型 φ(L)L と P の連結
L
∘
P
{\displaystyle L\circ P}
L と P の和集合
L
∪
P
{\displaystyle L\cup P}
L と（正規言語） D の積集合
L
∩
D
{\displaystyle L\cap D}
しかし、積集合や差集合に関しては閉じていない。これらの操作の具体的な内容については形式言語の情報工学的定義 を参照されたい。
積集合操作で閉じていないことの証明 文脈自由言語は積集合 において閉じていない。この証明は参考文献にある Sipser 97 の練習問題となっている。まず、2つの文脈自由言語
A
=
{
a
m
b
n
c
n
∣
m
,
n
≥
0
}
{\displaystyle A=\{a^{m}b^{n}c^{n}\mid m,n\geq 0\}}
B
=
{
a
n
b
n
c
m
∣
m
,
n
≥
0
}
{\displaystyle B=\{a^{n}b^{n}c^{m}\mid m,n\geq 0\}}
A
∩
B
=
{
a
n
b
n
c
n
∣
n
≥
0
}
{\displaystyle A\cap B=\{a^{n}b^{n}c^{n}\mid n\geq 0\}}
文脈自由言語の反復補題 を用いることで、それが文脈自由言語でないことを示すことができる。
決定性属性 文脈自由言語についての以下の問題は決定不能である。
等価性: 2つの文脈自由文法 A と B が与えられたとき、
L
(
A
)
=
L
(
B
)
{\displaystyle L(A)=L(B)}
L
(
A
)
∩
L
(
B
)
=
∅
{\displaystyle L(A)\cap L(B)=\emptyset }
L
(
A
)
=
Σ
∗
{\displaystyle L(A)=\Sigma ^{*}}
L
(
A
)
⊆
L
(
B
)
{\displaystyle L(A)\subseteq L(B)}
文脈自由言語についての以下の問題は決定可能である。
L
(
A
)
=
∅
{\displaystyle L(A)=\emptyset }
L(A) は有限か?
メンバーシップ: ある単語 w を与えたとき
w
∈
L
(
A
)
{\displaystyle w\in L(A)}
CYK法 を参照されたい）
参考文献
Michael Sipser (1997年). Introduction to the Theory of Computation . PWS Publishing. ISBN 0-534-94728-X .
