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

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

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

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

圖2 Chomsky層級

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