自动机、上下文无关语法以及音位重写规则之间究竟有什么联系呢？它们之间的共同之处在于都描写了一种形式语言（formal language），而形式语言是在有限字母表上的符号串集合。但是，我们用每个形式化方法写的语法的类别具有不同的生成能力（generative power）。如果一个语法能够定义一种语言，而另一种语法不能，我们就说这种语法比另一种语法具有更强的生成能力或更大的复杂性。例如，我们将说明，上下文无关语法能够描述的形式语言是有限状态自动机不能描述的。

我们可以建立语法的层级，其中具有较强语法描述能力的语言的集合蕴涵具有较弱语法描述能力的语言。可能的语法层级有很多,在计算语言学中最常用的是Chomsky层级（Chomsky,1959a）。Chomsky层级包含四种语法，如图1所示。

图1 Chomsky层级的语言文氏图（Venn diagram）

在直觉上不太明显的是：伴随着加在可重写语法规则上的约束的增加，语言的生成能力从最强降到最弱。下面的图2说明了Chomsky层级中的语法的四种类型，这些语法是通过规则形式的约束来定义的。在例子中，A是一个简单的非终极符号，a,β和y是由终极符号和非终极符号构成的任意符号串。除了特别提出不允许之外，它们可以为空，x是任意的终极符号串。

图2 Chomsky层级

0型语法或无限制语法除了要求规则的左部不能是空符号串ε之外，对于它们的规则的形式没有限制。任何非零的符号串都可以重写为任何其他符号串（或者ε）。0型语法刻画了递归可枚举语言(recursively enumerable language)，也就是说，0型语法生成的符号串可以由Turing机(Turing machine）列出（或枚举）。