上下文有關語言
在理論計算機科學中，上下文有關語言是可被上下文有關文法定義的形式語言。它是喬姆斯基譜系中的四類文法之一。它在理論和實踐中都是最少使用的。
計算性質
上下文有關語言的可計算性等價於線性有界非確定圖靈機。它是磁帶只有 kn 個單元的非確定圖靈機，這裡的 n 是輸入的大小而 k 是與這個機器關聯的常數。這意味着可以被這種機器判定的所有形式語言都是上下文有關語言，而所有上下文有關語言都可以被這種機器判定。
這種語言的集合也叫做 NLIN-SPACE，因為它們可以在非確定圖靈機上使用線性空間來接受。類 LIN-SPACE 定義相同，除了使用確定圖靈機之外。。明顯的 LIN-SPACE 是 NLIN-SPACE 的子集，但不知道是否 LIN-SPACE=NLIN-SPACE。普遍猜測它們是不相等的。
例子
不是上下文無關的上下文有關語言的一個例子是 L = { ap : p 是質數 }。證明它的最容易方式是使用線性有界圖靈機。
上下文有關語言的性質
- 兩個上下文有關語言的併集、交集和串接也是上下文有關的。
- 上下文有關語言的補集自身是上下文有關的。
- 所有上下文無關語言都是上下文有關的。
- 一個字符串在由任意上下文有關文法，或任何確定上下文有關文法所定義的語言中的成員關係是 PSPACE-完全問題。
參見
引用
- Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.