上下文無關語言

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

基本介紹

• 中文名：上下文無關語言
• 學科：計算機

例子

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

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

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

可判定性性質

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

等價：給定兩個上下文無關文法A 和 B，嗎？

嗎？

嗎？

嗎？

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

嗎？

L(A) 是有限的嗎？

成員關係：給定任何字 w，嗎？（成員關係問題甚至是多項式可判定的 - 參見CYK算法）

上下文無關語言的性質

• 上下文無關語言的反轉（reverse）也是上下文無關的，但是補（complement）不必須是。
• 所有正則語言都是上下文無關的，因為它們可以用正則文法描述。
• 存在不是上下文無關的上下文有關語言。
• 要證明給定語言不是上下無關的，可以採用上下文無關語言的泵引理。