上下文有關語言

理論計算機科學中,上下文有關語言是可被上下文有關文法定義的形式語言。它是喬姆斯基譜系中的四類文法之一。它在理論和實踐中都是最少使用的。

計算性質

上下文有關語言的可計算性等價於線性有界非確定圖靈機。它是磁帶只有 kn 個單元的非確定圖靈機,這裏的 n 是輸入的大小而 k 是與這個機器關聯的常數。這意味着可以被這種機器判定的所有形式語言都是上下文有關語言,而所有上下文有關語言都可以被這種機器判定。

這種語言的集合也叫做 NLIN-SPACE,因為它們可以在非確定圖靈機上使用線性空間來接受。類 LIN-SPACE 定義相同,除了使用確定圖靈機之外。。明顯的 LIN-SPACENLIN-SPACE 的子集,但不知道是否 LIN-SPACE=NLIN-SPACE。普遍猜測它們是不相等的。

例子

不是上下文無關的上下文有關語言的一個例子是 L = { ap : p質數 }。證明它的最容易方式是使用線性有界圖靈機。

上下文有關語言的性質

  • 兩個上下文有關語言的併集、交集和串接也是上下文有關的。
  • 上下文有關語言的補集自身是上下文有關的。
  • 所有上下文無關語言都是上下文有關的。
  • 一個字符串在由任意上下文有關文法,或任何確定上下文有關文法所定義的語言中的成員關係是 PSPACE-完全問題。

參見

引用

  • Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.