上下文無關語言

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

例子

一個原型上下文無關語言是  ,它是所有非空、偶數長度字符串的語言,字符串的整個前半部分都是  ,整個後半部分都是    由文法   生成,並被下推自動機   接受,這裏的   定義如下:


 
 
 
 
 
這裏的 z 是初始棧符號而 x 意味着彈出動作。


上下文無關語言在程式語言中有很多應用。大多數算術表達式可用上下文無關文法生成。

閉包性質

上下文無關語言閉合於下列運算下。就是說,如果 LP 是上下文無關語言而 D正則語言,下列語言也是上下文無關語言:

  • LKleene星號  
  • L字符串同態 φ 下的像 φ(L)
  • LP串接  
  • LP併集  
  • L 和(正則語言)D交集  

上下文無關語言不閉合於補集交集差集下。

在交集下不閉包

上下文無關語言不閉合於交集下。其證明在 Sipser 97 中被作為習題給出。選用語言   ,它們都是上下文無關的。它們的交集是  ,它可以用上下文無關語言的泵引理證實為非上下文無關的。

可判定性性質

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

  • 等價:給定兩個上下文無關文法 A 和 B,  嗎?
  •   嗎?
  •   嗎?
  •   嗎?

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

  •   嗎?
  • L(A) 是有限的嗎?
  • 成員關係:給定任何字 w,  嗎?(成員關係問題甚至是多項式可判定的 - 參見CYK算法

上下文無關語言的性質

引用