喬姆斯基層次結構

在形式語言理論、計算機科學和語言學中，喬姆斯基層次結構，是一種形式語法類的包含層次結構。

這種類型的形式語法由一組有限的生產規則（左手邊→右手邊）組成，其中每個邊由以下符號的有限序列組成。一組有限的非終端符號一組有限的終端符號一個起始符號形式語法為（或產生）形式語言提供了一個公理模式，它是一組（通常是無限的）有限長度的符號序列，可以通過對另一個符號序列（最初只包含起始符號）應用生產規則來構建。一條規則可以通過用出現在其右手邊的符號替換其左手邊的符號而被應用。一系列的規則應用被稱為一個派生。這樣的語法定義了形式語言：所有只由終端符號組成的詞，可以通過從起始符號開始的派生達到。非終端通常用大寫字母表示，終端用小寫字母表示，起始符號用S表示。例如，語法中的終端{a,b}，非終端{S,A,B}，生產規則S→ABS→ε（其中ε是空字符串）A→aSB→b和起始符號S，定義了所有形式的詞的語言再比如，英語的一個玩具子集的語法是這樣的。

句法不正確的句子不能從這個語法中導出。關于更多的自然語言例子和形式語法在該領域的問題，見句子結構語法和句子結構規則。

請注意，對應于遞歸語言的語法集不是這個層次的成員；這些語法將正確地介于Type-0和Type-1之間。每個常規語言都是無語境的，每個無語境語言都是語境敏感的，每個語境敏感語言都是遞歸的，每個遞歸語言都是可遞歸枚舉的。這些都是適當的內涵，也就是說，存在著非語境敏感的可遞歸列舉語言，非語境敏感的語言和非正則的無語境語言。

0型語法包括所有的形式語法。它們確切地產生了所有能被圖靈機識別的語言。這些語言也被稱為可遞歸列舉的語言或可被圖靈識別的語言。請注意，這與遞歸語言不同，遞歸語言可以由始終保持的圖靈機決定。