自動機、上下文無關(guān)語法以及音位重寫規(guī)則之間究竟有什么聯(lián)系呢？它們之間的共同之處在于都描寫了一種形式語言（formal language），而形式語言是在有限字母表上的符號串集合。但是，我們用每個形式化方法寫的語法的類別具有不同的生成能力（generative power）。如果一個語法能夠定義一種語言，而另一種語法不能，我們就說這種語法比另一種語法具有更強的生成能力或更大的復(fù)雜性。例如，我們將說明，上下文無關(guān)語法能夠描述的形式語言是有限狀態(tài)自動機不能描述的。

我們可以建立語法的層級，其中具有較強語法描述能力的語言的集合蘊涵具有較弱語法描述能力的語言。可能的語法層級有很多,在計算語言學(xué)中最常用的是Chomsky層級（Chomsky,1959a）。Chomsky層級包含四種語法，如圖1所示。

圖1 Chomsky層級的語言文氏圖（Venn diagram）

在直覺上不太明顯的是：伴隨著加在可重寫語法規(guī)則上的約束的增加，語言的生成能力從最強降到最弱。下面的圖2說明了Chomsky層級中的語法的四種類型，這些語法是通過規(guī)則形式的約束來定義的。在例子中，A是一個簡單的非終極符號，a,β和y是由終極符號和非終極符號構(gòu)成的任意符號串。除了特別提出不允許之外，它們可以為空，x是任意的終極符號串。

圖2 Chomsky層級

0型語法或無限制語法除了要求規(guī)則的左部不能是空符號串ε之外，對于它們的規(guī)則的形式?jīng)]有限制。任何非零的符號串都可以重寫為任何其他符號串（或者ε）。0型語法刻畫了遞歸可枚舉語言(recursively enumerable language)，也就是說，0型語法生成的符號串可以由Turing機(Turing machine）列出（或枚舉）。