上下文無關語言

上下文無關語言是可以用上下文無關文法定義的形式語言。所有上下文無關語言的集合同一於下推自動機所接受的語言的集合。

例子

一個原型上下文無關語言是 $L=\{a^{n}b^{n}:n\geq 1\}$，它是所有非空、偶數長度字符串的語言，字符串的整個前半部分都是 $a$，整個後半部分都是 $b$。$L$ 由文法 $S\to aSb~|~ab$ 生成，並被下推自動機 $M=(\{q_{0},q_{1},q_{f}\},\{a,b\},\{a,z\},\delta ,q_{0},\{q_{f}\})$ 接受，這裡的 $\delta$ 定義如下：

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

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

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

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

$\delta (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}\mid m,n\geq 0\}$ 和 $B=\{a^{n}b^{n}c^{m}\mid m,n\geq 0\}$，它們都是上下文無關的。它們的交集是 $A\cap B=\{a^{n}b^{n}c^{n}\mid n\geq 0\}$，它可以用上下文無關語言的泵引理證實為非上下文無關的。

可判定性性質

上下文無關語言的下列問題是不可判定的：

• 等價：給定兩個上下文無關文法 A 和 B，$L(A)=L(B)$ 嗎？
• $L(A)\cap L(B)=\emptyset$ 嗎？
• $L(A)=\Sigma ^{*}$ 嗎？
• $L(A)\subseteq L(B)$ 嗎？

上下文無關語言的下列問題是可判定的：

• $L(A)=\emptyset$ 嗎？
• L(A) 是有限的嗎？
• 成員關係：給定任何字 w，$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.