上下文有关语言

维基百科，自由的百科全书

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

[编辑] 计算性质

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

自动机理论: 形式语言和形式文法
乔姆斯基层级	文法	语言	极小自动机
类型 0	无限制	递归可枚举	图灵机
n/a	(无公用名)	递归	判定器
类型 1	上下文有关	上下文有关	线性有界
n/a	附标	附标	嵌套堆栈
n/a	树-邻接	适度上下文有关	嵌入下推
类型 2	上下文无关	上下文无关	非确定下推
n/a	确定上下文无关	确定上下文无关	确定下推
类型 3	正则	正则	有限
每个语言或文法范畴都是其直接上面的范畴的真子集。