跳至內容

上下文無關語言

維基百科,自由的百科全書

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

例子

[編輯]

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







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


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

閉包性質

[編輯]

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

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

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

在交集下不閉包

[編輯]

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

可判定性性質

[編輯]

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

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

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

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

上下文無關語言的性質

[編輯]

引用

[編輯]