上下文有关语言

文法分类（A hierarchy of Grammars）著名语言学家Noam Chomsky定义了四类文法和四种形式语言类，文法的四种类型分别是0型、1型、2型和3型。几类文法的差别在于对产生式施加不同的限制，分别是：

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

设G=(，，，)，如果它的每个产生式是这样一种结构： (∪)且至少含有一个非终结符，而(∪)，则G是一个0型文法。

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

设G=(，，，)为一文法，若中的每一个产生式均满足|，仅仅除外，则文法G是1型或上下文有关的。

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

设G=(，，，)，若P中的每一个产生式满足：是一非终结符，(∪)则此文法称为2型的或上下文无关的。

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

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

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

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

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

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