上下文有關語言

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

計算性質

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

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

例子

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

上下文有關語言的性質

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

參見

• 喬姆斯基層級
• 不收縮文法 – 完全的生成上下文有關語言
• 附標語言 – 上下文有關語言的嚴格子集

引用

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