上下文无关语言

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

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

${\displaystyle \delta (q_{0},a,z)=(q_{0},a)}$

${\displaystyle \delta (q_{0},a,a)=(q_{0},a)}$

${\displaystyle \delta (q_{0},b,a)=(q_{1},x)}$

${\displaystyle \delta (q_{1},b,a)=(q_{1},x)}$

${\displaystyle \delta (q_{1},b,z)=(q_{f},z)}$

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

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

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

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

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

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

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

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

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

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

• 上下文无关语言的反转（reverse）也是上下文无关的，但是补（complement）不必须是。
• 所有正则语言都是上下文无关的，因为它们可以用正则文法描述。
• 存在不是上下文无关的上下文有关语言。
• 要证明给定语言不是上下无关的，可以采用上下文无关语言的泵引理。

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