鴿子比籠子多
整個原理一口氣就能說完：如果你把 n+1 隻鴿子放進 n 個籠子，那麼至少有一個籠子最後裝了兩隻或更多。就這樣。它顯而易見到幾乎不配有個名字，然而鴿籠原理卻是這門學科最得力的主力之一。它全部的威力來自一個刻意製造的不對等——你安排了要存放的東西比存放的位置還多，然後一收網：兩個不同的東西被迫落到同一個位置。
用前幾篇指南的語言來說，這個原理是一個關於函數的事實。如果一個函數把大小為 m 的有限集合映入大小為 n 的有限集合，而 m > n，那麼這個函數不可能是嵌射的——必有兩個相異的輸入共用同一個輸出。鴿子就是輸入，籠子就是輸出，而「共用一個籠子」就只是「映到同一個值」。它還有一個量化版本，即廣義形式：若你把 m 隻鴿子分散到 n 個籠子，則某個籠子至少裝了 m/n 的上取整。把 10 隻鴿子放進 3 個籠子，某個籠子至少有 4 隻，因為一旦超過 9，你就無法讓每個籠子都維持在 3。
有限機器只有有限多個鴿籠
現在把它接到機器上，因為正是在這裡，這個原理不再只是個餘興把戲。回想階梯前段提過，DFA 是一台只記得自己當前狀態的販賣機——而它的狀態數是固定且有限的，比方說 k 個。狀態就是籠子。當機器讀一個字串時，每讀一個符號它就恰好處在某一個狀態，所以一段長度為 L 的執行會經過 L+1 個狀態（含起始狀態）。如果字串比機器的狀態數還長——也就是 L+1 > k——那麼根據鴿籠原理，同一個狀態必定被經過兩次。
那個被迫發生的單一重複，是關於有限記憶最深刻的事實，也正是有限記憶極限的確切內容：一台 DFA 無法無上限地計數，因為要計數它就得為每個值準備一個相異的狀態，而它只有有限多個。這裡的鴿子是輸入字串的前綴；籠子是它們落入的狀態。兩個落入同一狀態的不同前綴，對機器而言是無從分辨的——它已經實實在在地忘了自己讀的是哪一個。記住這個想法；它是你即將遇見的邁希爾–奈洛德定理的種子。
DFA with k = 3 states, reading a string of length 4 (5 states visited):
read: (start) a a a a
state: q0 -> q1 -> q2 -> q0 -> q1 -> q2
^^
5 visited states, only 3 distinct -> q0 repeats (and q1, q2 do too).
Pigeons = the 5 visited states. Holes = the 3 distinct states.
More pigeons than holes => a repeat is forced.幫浦引理是穿了戲服的鴿籠原理
看看那個被迫的重複替我們換來了什麼。假設一台有 k 個狀態的 DFA 接受某個長度至少為 k 的字串 s。讀 s 時，機器至少經過 k+1 個狀態，所以根據鴿籠原理某個狀態 q 重現了。在這兩次造訪 q 之處把字串切開：第一次造訪之前的部分是 x，兩次造訪之間讀到的那段符號迴圈是 y，其餘是 z，於是 s = x y z 且 y 非空。關鍵在於：讀完 y 之後，機器回到了完全相同的狀態 q。所以它分不出這個迴圈走零次、一次、還是一百次的差別——每個字串 x y^i z 都驅使它走過同一段接受性的執行。
那就是幫浦引理，從頭到尾。幫浦長度 p 就只是狀態數（任何 k 都行），而「長字串可以被幫浦」不過就是「長執行必定產生迴圈」。所以當第 2 篇指南要你否定一個五層深的量詞巢狀結構時，你所否定的那個東西，骨子裡正是這個鴿籠事實。引理的承諾——每個夠長的被接受字串都含有一個可重複的迴圈——是由計數所保證的：前綴太多、狀態太少。
- 取一個正規語言 L；根據定義，某台狀態數為有限 k 的 DFA 辨識它。令幫浦長度 p = k。
- 任取一個長度至少為 p 的被接受字串 s。讀它會經過至少 p+1 = k+1 個狀態。
- 鴿籠原理：經過的狀態比相異狀態多，所以在前 p 個符號內，某個狀態 q 至少被造訪了兩次。
- 把 s 切成 x y z，其中 y 是兩次造訪 q 之間讀到的迴圈（所以 y 非空且 |xy| <= p）。機器在 y 之前與之後都處在狀態 q。
- 由於這個迴圈回到 q，重複或刪去它都不會改變機器能察覺的任何東西：對每個 i >= 0，x y^i z 都被接受。這恰恰就是幫浦的結論。
讓它上工：為什麼 a^n b^n 辦不到
這就是回報，是「有限機器無法把 a 和 b 配對」的證明。取語言 a^n b^n——若干個 a 後面接著恰好同樣多的 b。為了反證，假設它是正規的，於是某台有 k 個狀態的 DFA 接受它。餵給它字串 a^k b^k。在它讀前 k 個 a 的過程中，它經過 k+1 個狀態，所以根據鴿籠原理，它還在那串 a 之內時就重複了某個狀態。那兩次造訪之間的迴圈完全由 a 組成。把那個迴圈多幫浦一次，你就得到比 b 還多的 a——一個機器照樣接受、卻不是 a^n b^n 形式的字串。矛盾：這樣的 DFA 不存在，所以這個語言不是正規的。
注意我們從不需要點出那個重複的狀態、也不需要精確計算迴圈落在哪——鴿籠原理免費奉送了「在那串 a 之中某處存在一次重複」，而論證需要的也僅此而已。這是幾乎每一個非正規性證明的範本：挑一個字串，讓它的結構把可幫浦的迴圈逼進一個區域，使得在那裡幫浦必定破壞原本的樣式。整個過程中的直覺既貼近人性又具體：要檢查 b 的數目和 a 相符，你就得記住自己看到了多少個 a，而一個固定的有限記憶就是會用光空間。
同一個想法，一再出現
一旦你練出辨識它的眼力，鴿籠原理就會在每一處「有限資源對上無上限需求」的地方現身。邁希爾–奈洛德定理把這個想法變成一個精確的分類：如果一個語言迫使無窮多個前綴兩兩可分辨——每個都需要自己的狀態——那麼沒有任何有限機器能裝下它們全部，於是該語言不是正規的。那就是鴿籠原理從一次性的技巧升格成一個完整的刻畫。同樣的形狀，有限多個狀態對上無窮多個要記住的東西，也驅動了 DFA 大小的下界。
這個原理也伸展到正規語言之外。它的大哥驅動了上下文無關語言的幫浦引理——一棵夠深的剖析樹，在某條由根到葉的路徑上必定含有一個重複的非終端符號，因為樹很深而非終端符號的供應是有限的，於是某個子樹可以被幫浦。不同的機器，同樣的邏輯：一份有限的建材清單加上一個無上限的結構，就會逼出重複。每當你看見「夠長就逼出重複」，你看到的就是一隻鴿子和一個籠子。
最後一個值得分清楚的對照。鴿籠原理處理的是有限對有限的擠壓：在有限的集合之間，鴿子比籠子多。下一篇指南轉向無限——康托爾的對角線論證——在那裡，令人驚訝的是即使兩個無限集合也可能配不起來，而某些語言竟然根本沒有任何機器能對應。鴿籠原理告訴你有限機器會遺忘；對角線論證告訴你有些任務超出了每一台機器的能耐。兩者合起來，就是釘住計算極限的那兩個計數論證。