設計出機器的那唯一一個問題
在第 2 篇，你已確定了 DFA「是什麼」——那個五元組、轉移函數 δ（希臘字母 delta，動作的規則手冊），以及「字串的計算停在接受狀態時即被接受」這條規則。那些教你如何讀懂一部現成的機器，卻還沒教你如何從「含有 011 的字串」或「a 的個數為偶數」這類白話描述造出一部。本篇談的正是這一躍，而好消息是：它幾乎全部都從一個問題流瀉而出。
問題就是這個，而它妙在極為具體：當我由左到右、一次一個符號地掃描輸入時，為了日後能決定該不該接受，我到目前為止最少必須記住什麼？ DFA 唯一的記憶就是它目前的狀態，所以這個問題每一個不同的答案——過往可能把你留在的每一種真正不同的「情境」——都必須成為一個狀態。把情境清單列對，機器幾乎是自己畫出來的；列錯了，再怎麼擺弄箭頭也救不回來。
暖身：奇偶性，與四步驟食譜
看「在 {a, b} 上、a 的個數為偶數的字串」這個語言。套用那個問題：要在最後知道 a 的個數是否為偶，我必須一路帶著什麼？不是計數本身——那會無界地增長——而只要它的奇偶性：目前為止的計數是偶是奇？那是一個位元、兩種情境，所以兩個狀態：E（「目前 a 的個數為偶」）與 O（「目前 a 的個數為奇」）。整個無界的計數塌縮成單一個位元，而這個塌縮正是 DFA 設計的核心。
- 列出你必須追蹤的事實，每一種不同的情境設一個狀態。此處：E 與 O，即 a 個數的奇偶性。
- 選起始狀態時，問「空輸入時什麼為真」。零個 a 是偶數，所以從 E 開始。（DFA 對 epsilon，也就是空字串，的裁決也是在這裡決定的。）
- 填入 δ：對每個狀態與符號，問你接下來落入哪種情境。讀 b 從不改變 a 的個數，所以在兩個狀態上都是自迴圈；讀 a 翻轉奇偶，所以 δ(E,a)=O、δ(E,b)=E、δ(O,a)=E、δ(O,b)=O。
- 標記接受狀態——意味成功的那些情境。「a 的個數為偶數」表示 F = {E}。完成：一部正確的兩狀態 DFA。
留意最後一步有多有彈性。保留完全相同的狀態與 δ，只把接受集合翻成 F = {O}，這部機器現在辨識的就是「a 的個數為奇數」。狀態負責記憶；F 只決定你願意把哪些記住的事實稱作「是」。這種分離——情境，相對於「哪些情境算贏」——值得記在心裡，因為它正是下一篇的乘積構造法用來結合多個條件的手法。
對 k 取餘的計數：記餘數，而非總數
奇偶性其實就是對 2 取餘，而同樣的把戲可以放大。假設我們想要其數值可被 3 整除的二進位字串（在 {0, 1} 上，最高位元先讀）。數值可以大到天文數字，遠遠大到存不下。但再問那個問題：我最少必須記住什麼？答案是目前所見數值對 3 取的餘數——只有三種可能之一：0、1 或 2。三種情境，三個狀態：r0、r1、r2。
為什麼餘數夠用，而數值本身卻不夠？因為「在尾端接上一個位元」如何改變數值：讀到位元 d，會把數值 v 變成 2v + d。而 2v + d 對 3 取的餘數，只取決於 v 對 3 取的餘數（以及 d）——絕不取決於完整的數值。所以轉移純粹是餘數的算術：從餘數 r 讀到位元 d，就走到餘數 (2r + d) mod 3。這就是整部機器。這是模算術日常般的奇蹟，替 DFA 把帳記好了。
Language: binary strings whose value is divisible by 3 (MSB first)
States = remainder mod 3 of the value read so far.
Transition rule: from r, on bit d, go to (2*r + d) mod 3.
| bit 0 | bit 1
----- +------------- +-------------
-> r0*| (2*0+0)=0 r0 | (2*0+1)=1 r1
r1 | (2*1+0)=2 r2 | (2*1+1)=3 r0 (3 mod 3 = 0)
r2 | (2*2+0)=4 r1 | (2*2+1)=5 r2 (4 mod 3 = 1, 5 mod 3 = 2)
-> marks the start state (r0) * marks the accept state (r0)
Trace 110 (= six, divisible by 3): r0 -1-> r1 -1-> r0 -0-> r0 -> accept
Trace 101 (= five): r0 -1-> r1 -0-> r2 -1-> r2 -> reject這個模式立刻就能推廣：對「可被 k 整除」用 k 個狀態 r0、…、r(k-1)，從 r0 開始、接受 r0，並讓「讀一個符號」去更新餘數。這是最乾淨的示範，說明為何這類語言儘管含有無限多個字串，卻仍是正規的——有界的記憶（k 個餘數之一）真的就夠用，無論那個數變得多長、多大。
子字串、重疊，與「退太遠」的陷阱
現在來談實務上最有用的模式：辨識含有固定子字串的字串，比方在 {0, 1} 上某處含有 011。要追蹤的事實是「到此為止、以此刻結尾，我已配對到 011 的多少？」。這給出四種情境：沒配到有用的（s0）、已配到 0（s1）、已配到 01（s2）、找到 011（s3，成功）。一旦到達 s3，答案就已是「是」、且永遠不可能再變成「否」，所以 s3 對每個符號都迴圈到自己——一個永久的「成功匯點」。
讀到「錯的」符號時的轉移，是幾乎人人都會失足之處。在 s2（「我剛看到 01」）時讀到一個 0。你很容易想要一路退回 s0——但那是錯的，因為你剛讀到的這個 0，本身就是一次可能的新配對的起點。正確的動作是走到 s1（「已配到 0」）。你必須永遠問：讀完這個符號後，以此刻結尾、011 最長的前綴是什麼？把一個其實還能再利用的部分配對丟掉，正是那個經典的臭蟲，而這正是字串搜尋演算法也必須處理的那種重疊。
把要求翻成「不含 011」，你照樣沿用這同一套四情境追蹤——只不過現在 s3 這個「找到了」的狀態變成了壞結果。它變成一個非接受的陷阱狀態（也叫死狀態）：一旦看到 011，字串就注定失敗，所以 s3 永遠迴圈到自己、且永不接受，而 s0、s1、s2 全部接受。陷阱正是 DFA 一邊禮貌地讀完剩下的輸入、一邊記下「違規已發生」的方式；它也讓 δ 保持全函數，意思是每個（狀態, 符號）對都有定義好的動作，機器永不卡住。
結合條件，與一道你無法繞過去的極限
真實的規格常把好幾個條件黏在一起：「a 的個數為偶數且字串以 b 結尾」，或「可被 3 整除或含有 011」。你可以試著從零開始、列出每一種組合情境來設計這樣的機器，但有個機械化的捷徑。把兩部現成的機器並排執行，同時為各自保留一個狀態；組合機器的單一狀態就是一個有序對（每個條件對應一個分量）。這就是乘積構造法，也是下一篇的全部主題——這裡只要注意：「同時記住兩件事」本身不過就是「記住那個有序對」，而它仍然是一個有限的情境集合。
目前為止每個例子都行得通，是因為「要記住的東西」是有界的：一個奇偶位元、k 個餘數之一、四個配對進度階段之一，或這些的有序對。這並非偶然——它正是這個模型的確切觸及範圍，而它有一道硬邊界。誠實的極限就是有限記憶極限：DFA 無法無界地計數。 如果一個語言要求追蹤一個無界的量，再怎麼選狀態也沒用。
經典例子是語言 a^n b^n（n 個 a 後面接恰好 n 個 b，n 為任意數）。要把 b 的個數與 a 的個數核對，一部正在讀 b 的機器必須記得前面來了多少個 a——而 n 可以任意大。無論狀態數固定為多少，兩個不同的 a 個數終究必定落入同一個狀態（這是喬裝過的鴿籠原理），此後機器對兩者的行為完全相同，被迫誤判其中之一。所以沒有任何 DFA 辨識 a^n b^n；它不是正規的。關鍵在於「無界」這個詞才是要害：DFA 能檢查「至多 1000 個 a」（用足夠多的狀態即可）——它失敗，只在於那個界限本身被允許是任何數字。這道界線、以及逃出它的工具（一個堆疊），正是後面幾級所建立的基礎。