上下文有关语言

理论计算机科学中,上下文有关语言是可被上下文有关文法定义的形式语言。它是乔姆斯基谱系中的四类文法之一。它在理论和实践中都是最少使用的。

计算性质

上下文有关语言的可计算性等价于线性有界非确定图灵机。它是磁带只有 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.