複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/上下文無關語言/23121004
複製
複製成功

上下文無關語言

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

目錄

  1. 1 例子
  2. 2 可判定性性質
  3. 3 上下文無關語言的性質

上下文無關語言例子

一個原型上下文無關語言是
，它是所有非空、偶數長度字符串的語言，字符串的整個前半部分都是a，整個後半部分都是b。L由文法
生成，並被下推自動機
接受，這裏的
定義如下：
這裏的 z 是初始棧符號而 x 意味着彈出動作。
上下文無關語言在編程語言中有很多應用。大多數算術表達式可用上下文無關文法生成。

上下文無關語言可判定性性質

上下文無關語言的下列問題是不可判定的：
等價：給定兩個上下文無關文法A 和 B，
嗎？
嗎？
嗎？
嗎？
上下文無關語言的下列問題是可判定的：
嗎？
L(A) 是有限的嗎？
成員關係：給定任何字 w，嗎？（成員關係問題甚至是多項式可判定的 - 參見CYK算法）

上下文無關語言上下文無關語言的性質

  • 上下文無關語言的反轉（reverse）也是上下文無關的，但是補（complement）不必須是。
  • 所有正則語言都是上下文無關的，因為它們可以用正則文法描述。
  • 存在不是上下文無關的上下文有關語言。
  • 要證明給定語言不是上下無關的，可以採用上下文無關語言的泵引理。 [1] 
參考資料
  • 1.    Michael Sipser. Introduction to the Theory of Computation. PWS Publishing. 1997. ISBN 0-534-94728-X. Chapter 2: Context-Free Languages, pp.91–122.