跳转到内容

上下文无关语言

维基百科,自由的百科全书

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

例子

一个原型上下文无关语言是 ,它是所有非空、偶数长度字符串的语言,字符串的整个前半部分都是 ,整个后半部分都是 由文法 生成,并被下推自动机 接受,这里的 定义如下:







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


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

闭包性质

上下文无关语言闭合于下列运算下。就是说,如果 LP 是上下文无关语言而 D正则语言,下列语言也是上下文无关语言:

  • LKleene星号
  • L字符串同态 φ 下的像 φ(L)
  • LP串接
  • LP并集
  • L 和(正则语言)D交集

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

在交集下不闭包

上下文无关语言不闭合于交集下。其证明在 Sipser 97 中被作为习题给出。选用语言 ,它们都是上下文无关的。它们的交集是 ,它可以用上下文无关语言的泵引理证实为非上下文无关的。

可判定性性质

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

  • 等价:给定两个上下文无关文法 A 和 B, 吗?
  • 吗?
  • 吗?
  • 吗?

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

  • 吗?
  • L(A) 是有限的吗?
  • 成员关系:给定任何字 w, 吗?(成员关系问题甚至是多项式可判定的 - 参见CYK算法

上下文无关语言的性质

引用