可計算性和複雜性/形式語言/喬姆斯基層次結構
喬姆斯基層次結構是一組四個形式語言類，每個類都是上面類別的真子集，並且每個類都對應於一個生成語法和一個識別機器。這個層次結構主要源於 諾姆·喬姆斯基 和 馬塞爾-保羅·舒岑伯格 在 1950 年代後期關於機制語言學和形式語言的研究。層次結構的各個級別在理論計算機科學和應用計算機科學中都非常有用，因為它們與艾倫·圖靈關於演算法和可計算性的工作以及編譯器設計有關。
這個層次結構的每個級別都包含一類形式語言、一類生成語法（每個語法產生關聯類中的語言）和一類機器（每個機器識別關聯類中的語言）。在層次結構的每個級別，生成語法的規則變得更加嚴格，使每類語言成為上面類別的子集。這四個類，從最嚴格到最不嚴格，分別是