喬姆斯基階層（Chomsky hierarchy）
/ Chomsky is pronounced CHOM-skee /
喬姆斯基階層是整門學科的地圖：四個層層相套的盒子，依「處理某語言需要多少計算能力」把語言分類。想像四個一個套一個畫出的環，像俄羅斯套娃。最內層的環裝最簡單的語言，每往外一層就藉由允許更強大的機器而加入更多語言。本課程後面的每個主題都落在這張地圖上的某處，這就是值得及早認識它的原因。
由小到大，四個類別是：正規語言（最內）、上下文無關語言、上下文相關語言，以及遞迴可枚舉語言（最外）。每一個都是下一個的真子集，所以正規在上下文無關之內、在上下文相關之內、在遞迴可枚舉之內，而每一步確實都加入了較小類別碰不到的新語言。每個類別都配有一種「恰好識別它」的機器與一種「恰好生成它」的文法：正規語言配有限自動機與正規表示式；上下文無關語言配下推自動機（有限自動機加一個堆疊）與上下文無關文法；上下文相關語言配線性有界自動機；遞迴可枚舉語言配圖靈機，這是最一般的模型。所以攀爬這個階層，等同於給機器更多記憶體與更多自由。
兩點誠實的提醒讓這張地圖有用而非誤導。第一，正規不代表「小」或「有限」：正規語言可以是無限的（例如所有 a 構成的字串，a*），它只是表示「能用有限記憶體識別」。第二，這些包含關係的嚴格性是一個真正的定理，藉由展示分隔範例來證明：a^n b^n 是上下文無關但非正規，而 a^n b^n c^n 是上下文相關但非上下文無關。在最外環之外，坐落著連圖靈機都無法識別的語言，那裡正是可計算性理論與停機問題接手的地方。
a* 是正規。a^n b^n 是上下文無關但非正規。a^n b^n c^n 是上下文相關但非上下文無關。「對給定輸入會停機的所有圖靈機」的集合是遞迴可枚舉但不可判定。
四個嚴格相套的類別，各自配有一種識別機器與一種文法。
正規不代表有限。正規語言可以是無限的；這個詞的意思是「能被有限自動機識別」。四個包含關係是嚴格的，這是已證明的事實，不只是約定。