上下文无关语言

上下文无关语言是可以用上下文无关文法定义的形式语言。所有上下文无关语言的集合同一于下推自动机所接受的语言的集合。

例子

一个原型上下文无关语言是 $L = {a^{n} b^{n} : n \geq 1}$ ，它是所有非空、偶数长度字符串的语言，字符串的整个前半部分都是 $a$ ，整个后半部分都是 $b$ 。 $L$ 由文法 $S \to a S b | a b$ 生成，并被下推自动机 $M = ({q_{0}, q_{1}, q_{f}}, {a, b}, {a, z}, δ, q_{0}, {q_{f}})$ 接受，这里的 $δ$ 定义如下：

δ (q_{0}, a, z) = (q_{0}, a)

δ (q_{0}, a, a) = (q_{0}, a)

δ (q_{0}, b, a) = (q_{1}, x)

δ (q_{1}, b, a) = (q_{1}, x)

δ (q_{1}, b, z) = (q_{f}, z)

这里的 z 是初始栈符号而 x 意味着弹出动作。

上下文无关语言在编程语言中有很多应用。大多数算术表达式可用上下文无关文法生成。

闭包性质

上下文无关语言闭合于下列运算下。就是说，如果 L 和 P 是上下文无关语言而 D 是正则语言，下列语言也是上下文无关语言：

L 的 Kleene星号 $L^{*}$
L 在字符串同态 φ 下的像 φ(L)
L 和 P 的串接 $L \circ P$
L 和 P 的并集 $L \cup P$
L 和（正则语言）D 的交集 $L \cap D$

上下文无关语言不闭合于补集，交集或差集下。

在交集下不闭包

上下文无关语言不闭合于交集下。其证明在 Sipser 97 中被作为习题给出。选用语言 $A = {a^{m} b^{n} c^{n} ∣ m, n \geq 0}$ 和 $B = {a^{n} b^{n} c^{m} ∣ m, n \geq 0}$ ，它们都是上下文无关的。它们的交集是 $A \cap B = {a^{n} b^{n} c^{n} ∣ n \geq 0}$ ，它可以用上下文无关语言的泵引理证实为非上下文无关的。

可判定性性质

上下文无关语言的下列问题是不可判定的：

等价：给定两个上下文无关文法 A 和 B， $L (A) = L (B)$ 吗？
$L (A) \cap L (B) = \emptyset$ 吗？
$L (A) = Σ^{*}$ 吗？
$L (A) \subseteq L (B)$ 吗？

上下文无关语言的下列问题是可判定的：

$L (A) = \emptyset$ 吗？
L(A) 是有限的吗？
成员关系：给定任何字 w， $w \in L (A)$ 吗？（成员关系问题甚至是多项式可判定的 - 参见CYK算法）