可计算枚举语言被命名为0-型语言，上下文相关语言被命名为1-型语言，上下文无关语言被命名为2-型语言，正则语言被命名为3-型语言。低型语言不是高型的，默认情况下，每个高型的语言都是低型的，这个被称为乔姆斯基分层。

存在正则语言的一个扩展。在正则语言里，一个非终结符号可以像串最右端符号那样出现任一生成式的右边。这种语法也叫作右线性语法(right linear grammars)。当语法中每个生成式最多有一个非终结符在它右边，并且非终结符像最左端符号那样出现左边时，语法叫作左线性语法(1eft linear grammar)。在线性语法中，每个生成式在右边之多有一个非终结符，在位置上则无任何限制。

可以证明，线性语言，即由线性语法生成的语言，形成了上下文无关语言的一个子集。

很显然，每个正则语言都是线性的。线性语言类与确定性上下文无关语言不同。这些结果总结起来叫作乔姆斯基层次结构(Chomsky’s Hierarchy)。它规定：

每一个正则语言都是线性的。

每一个正则语言都是确定性上下文无关的。

每一个线性语言都是上下文无关的。

每一个确定性上下文无关语言都是上下文无关的。

每一个上下文无关语言都是上下文相关的。

每一个上下文相关语言都是可判定的。

每一个可判定语言都是可计算枚举的。

此外，先前说明的语言类之间的包含关系是固有的。其意味着：

存在可计算枚举语言是不可判定的。

存在可判定语言是非上下文相关的。

存在上下文相关语言是非上下文无关的。

存在上下文无关语言不是确定性上下文无关的。

存在上下文无关语言不是线性的。

存在确定性上下文无关语言不是正则的。

存在线性语言不是正则的。

存在确定性上下文无关语言不是线性的。

存在线性语言不是确定性上下文无关的。

线性有界自动机是非确定性图灵机带上线性空间的约束。相似的约束在确定性图灵机上随之产生了所谓的确定性线性有界自动机(deterministic linear bounded automata)。还未知的是，确定性线性有界自动机接受语言是否构成那些(非确定性)线性有界自动机接受语言的子集。

设定一个字母表三。设RE，REC，CS，CF，LIN，DCF，REG各自分别表示语言类包括三上所有可计算枚举(递归可枚举的)、可判定(递归)、上下文相关、上下文无关、线性、确定性上下文无关，和正则语言。乔姆斯基层次结构可以写成更进一步地，正则语言那些能被有限自动机接受的；上下文无关语言是那些被叠加自动机接受的；上下文相关语言是那些被线性有界自动机接受的；可计算枚举语言是那些被图灵机接受的。

由于这个层次结构，可计算枚举语言被命名为0-型语言，上下文相关语言被命名为1-型语言，上下文无关语言被命名为2-型语言，正则语言被命名为3-型语言。低型语言不是高型的，默认情况下，每个高型的语言都是低型的。这个被称为乔姆斯基层次结构，而上述阐明的结果构成了扩展的乔姆斯基层次结构。

在计算机科学中，形式语言是某个字母表上一些有限长字串的集合，而形式文法是描述这个集合的一种方法。形式文法之所以这样命名，是因为它与人类自然语言中的文法相似的缘故。最常见的文法的分类系统是乔姆斯基(Chomsky N)于1950年发展的乔姆斯基谱系，这个分类谱系把所有的文法分成四种类型：短语结构文法、上下文有关文法、上下文无关文法和正规文法。任何语言都可以由无限制文法来表达，余下的三类文法对应的语言类分别是递归可枚举语言、上下文无关语言和正规语言。依照排列次序，这四种文法类型依次拥有越来越严格的产生式规则，所能表达的语言也越来越少。尽管表达能力比短语结构文法和上下文相关文法要弱，但由于能高效率的实现，上下文无关文法和正规文法成为四类文法中最重要的两种文法类型。

短语结构文法是一种非受限文法，也称为0型文法，是形式语言理论中的一种重要文法。

正则文法来源于20世纪50年代中期乔姆斯基对自然语言的研究，是乔姆斯基短语结构文法分层里的3型文法。正则文法类是上下文无关(2型)文法类的真子类，已应用于计算机程序语言编译器的设计、词法分析(文本处理中描述触发过程动作的文本模式、文件类型和扫描器、文本工具的标准基础)、开关电路设计、句法模式识别等，是计算机和信息科学、工程、物理、化学、生物、医学、应用数学不可忽视的论题。

正则文法有多种等价的定义，可以用“左线性文法”或者“右线性文法”来等价地定义正则文法。“左线性文法”要求产生式的左侧只能包含一个非终结符号，产生式的右侧只能是空串、一个终结符号或者一个非终结符号后随一个终结符号。“右线性文法”要求产生式的左侧只能包含一个非终结符号，产生式的右侧只能是空串、一个终结符号或者一个终结符号后随一个非终结符号。