[科普中国]-上下文有关语言

文法分类（A hierarchy of Grammars）著名语言学家Noam Chomsky定义了四类文法和四种形式语言类，文法的四种类型分别是0型、1型、2型和3型。

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

文法内容几类文法的差别在于对产生式施加不同的限制，分别是：

* 0型文法(短语结构文法)(phrase structure grammars)：

设G =（VN，VT，P，S），如果它的每个产生式是这样一种结构：α∈(VN∪VT)* 且至少含有一个非终结符，而β∈(VN∪VT)*，则G是一个0型文法。

* 1型文法（上下文有关文法）(context-sensitive grammars)：

设G =（VN，VT，P，S）为一文法，若中的每一个产生式均满足|β|>=|α|，仅仅α→ε除外，则文法G是1型或上下文有关的。

* 2型文法（上下文无关文法）(context-free grammars)：

设G =（VN，VT，P，S），若P中的每一个产生式满足：α是非终结符，β∈(VN∪VT)*，同时又满足1型文法的条件，则此文法称为2型的或上下文无关的。

* 3型文法（正规文法）(regular grammars)：

设G =（VN，VT，P，S），若中的每一个产生式的形式都是A→aB或A→a，其中A和B都是非终结符，a是终结符，则G是3型文法或正规文法。

0型文法产生的语言称为0型语言。

1型文法产生的语言称为1型语言，也称作上下文有关语言。

2型文法产生的语言称为2型语言，也称作上下文无关语言。

3型文法产生的语言称为3型语言，也称作正规语言。1

计算性质上下文有关语言的可计算性等价于线性有界非确定图灵机。它是磁带只有kn个单元的非确定图灵机，这里的n是输入的大小而k是与这个机器关联的常数。这意味着可以被这种机器判定的所有形式语言都是上下文有关语言，而所有上下文有关语言都可以被这种机器判定。

这种语言的集合也叫做NLIN-SPACE，因为它们可以在非确定图灵机上使用线性空间来接受。类LIN-SPACE定义相同，除了使用确定图灵机之外。。明显的LIN-SPACE是NLIN-SPACE的子集，但不知道是否LIN-SPACE=NLIN-SPACE。普遍猜测它们是不相等的。1

上下文有关语言的性质两个上下文有关语言的并集、交集和串接也是上下文有关的。

上下文有关语言的补集自身是上下文有关的。

所有上下文无关语言都是上下文有关的。

一个字符串在由任意上下文有关文法，或任何确定上下文有关文法所定义的语言中的成员关系是PSPACE-完全问题。1

本词条内容贡献者为:

黎明 - 副教授 - 西南大学