上下文无关语言

(重定向自上下文無關語言

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

例子

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


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


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

闭包性质

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

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

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

在交集下不闭包

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

可判定性性质

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

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

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

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

上下文无关语言的性质

引用