上下文无关语言是可以用上下文无关文法定义的形式语言。所有上下文无关语言的集合同一于下推自动机所接受的语言的集合。
例子
一个原型上下文无关语言是 L = \{a^nb^n:n\geq1\}，它是所有非空、偶数长度字符串的语言，字符串的整个前半部分都是 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）不必须是。
- 所有正则语言都是上下文无关的，因为它们可以用正则文法描述。
- 存在不是上下文无关的上下文有关语言。
- 要证明给定语言不是上下无关的，可以采用上下文无关语言的泵引理。
引用
- Chapter 2: Context-Free Languages, pp.91–122.
评论 (0)