DFA 的有限記憶極限（the finite-memory limit of a DFA）

關於 DFA，初學者必須內化的最深刻一點，是它「不能」做什麼、以及為什麼。DFA 只有有限多個狀態，而一個狀態就是它的全部記憶。所以 DFA 只能記住有界的資訊量——它能數到某個固定上限、能追蹤一個餘數、能記住最後幾個符號，卻無法保有一個無界增長的累計。根本就沒有地方放一個無止盡變大的數字。

最乾淨的例子是括號配對，或它精簡過的表親語言 { a^n b^n : n >= 0 }（n 個 a 後面接恰好 n 個 b）。要接受它，一部正在讀 b 的機器必須記得前面來了多少個 a——而 n 可以任意大。假設機器只有 100 個狀態，到 b 來臨時它無法分辨 a^100 與 a^101：由鴿籠原理，兩個不同的 a 個數必定匯入同一個狀態，此後機器的行為完全相同，被迫對兩者一視同仁地接受或拒絕，於是必定弄錯其中之一。因此沒有任何 DFA 辨識 a^n b^n；這個語言不是正規的。

這不是一個有待修補的缺陷，而是這個模型的定義性界線。辨識任意深度的配平括號，需要一個能隨輸入增長的記憶——這正是堆疊所提供的，也正是為何下一個、更強的模型（下推自動機）加了一個堆疊。把「DFA 不能無界地計數」內化於心，能讓你在浪費時間之前就知道：某個問題何時超出有限狀態機的能力，以及該改拿哪件工具。