上下文無關語言在階層中的位置（hierarchy placement）

把語言家族想成一層套一層的俄羅斯娃娃，每一個都「嚴格」住在下一個之內。在喬姆斯基階層（Chomsky hierarchy）較小的娃娃當中，坐著三個你現在已經熟悉的：正規語言（regular language）、確定型上下文無關語言（deterministic context-free language, DCFL）、以及完整的上下文無關語言（context-free language）。它們排成一條嚴格的鏈——正規嚴格住在 DCFL 之內，DCFL 嚴格住在上下文無關之內——而「嚴格住在之內」意味著每一步都加進了較小類別確實到不了的語言。

帶著見證走一遍這條鏈。每個正規語言都是上下文無關（有限自動機是一台從不碰堆疊的下推自動機），但 { a^n b^n } 是上下文無關而「不」是正規——堆疊買到了真正的新能力，所以正規嚴格住在其他類別之內。每個 DCFL 都是上下文無關，但有些上下文無關語言不是確定型的：偶數長度的回文式複製語言 { w w^R } 需要「猜」中點，這是確定型下推自動機（DPDA）辦不到、而非確定型 PDA 辦得到的——所以 DCFL 嚴格住在 CFL 之內。而 { a^n b^n } 本身是一個不是正規的 DCFL，把前兩層分開。（與有限自動機不同——其確定型與非確定型版本同樣強大——確定型與非確定型「下推」自動機「並不」等價，確定型那個嚴格更弱。）

上方那道牆同樣重要：{ a^n b^n c^n } 根本「不」是上下文無關，把它放在整條鏈之上的上下文相關（context-sensitive）類別裡。所以圖像是 正規 ⊂ DCFL ⊂ 上下文無關 ⊂ 上下文相關，每個包含都是嚴格的，每道縫隙都有一個具體語言作見證。這個定位解釋了設計上的取捨：正規工具（正規表示式、有限自動機）快，但不能計數與比對；上下文無關工具（文法、PDA）能巢狀與平衡，卻在三方計數與像等價這樣的不可判定問題上撞牆。