從一種感覺到五個部件
在前一篇導覽中，你以一種感覺認識了有限狀態機：一道旋轉閘門、一個電燈開關、一台販賣機，除了它此刻所處的那一個狀態之外，對自己的歷史毫無記憶。這個直覺完全正確，但一種「感覺」無法被證明、無法餵給電腦、也無法在教科書裡拿來爭辯。所以這篇導覽要做件成熟的事——把那道旋轉閘門變成一個精確的數學物件，叫做確定型有限自動機，簡稱 DFA。概念上沒有任何新東西發生；我們只是把那道閘門寫得夠仔細，仔細到再也沒有揮手帶過的餘地。
整台機器恰好打包成五樣東西，依慣例寫成一個 五元組（Q, Σ, δ, q0, F）。別被希臘字母嚇到——每一格都是你早已從旋轉閘門那裡理解的東西。Q 是有限的狀態集合（機器可以處於的那些「心情」）。Σ（Sigma）是輸入字母表（它讀的符號，就是基礎那一階的那些字母表）。δ（delta）是轉移函數（描述每按下一個符號會把你送往哪裡的接線）。q0 是起始狀態（開機時所處的心情）。而 F 是接受狀態的集合（代表「是」的那些心情）。這就是整台機器了——一個盒子上的五個標籤。
轉移函數 δ 的兩種畫法
機器的核心是轉移函數 δ。我們把單一步驟寫成 delta(q, a) = p，唸作「從狀態 q 讀到符號 a，前往狀態 p」。如果 Q 有 3 個狀態、Σ 有 2 個符號，那麼 δ 必須回答 3 乘 2 = 6 個這樣的問題——每一個「狀態與符號」的配對各一個——而且它必須把每一個都回答到。把這些答案攤開來有兩種標準方式，而它們說的是一模一樣的事：狀態圖（一張圖）與轉移表（一個表格）。
狀態圖把每個狀態畫成一個圓圈，把每個轉移畫成圓圈之間一條標了字的箭頭。三個小慣例就承載了所有額外資訊：起始狀態 q0 有一支「從無到有」射進來的小箭頭；屬於 F 的接受狀態畫成雙重圓圈；而箭頭上的標籤就是觸發它的符號。為了把我們的範例畫出來，取 Σ = {a, b} 上的語言「偶數個 a」。兩個狀態就夠了：q_even（到目前為止看過偶數個 a）與 q_odd。讀到 a 會在兩者之間翻轉；讀到 b 則讓你留在原地。從 q_even 出發，並讓 q_even 成為唯一的接受狀態。
Language: strings over {a,b} with an EVEN number of a's.
State diagram (in words):
->( q_even )) <-- start AND accept (double circle)
q_even --a--> q_odd q_even --b--> q_even
q_odd --a--> q_even q_odd --b--> q_odd
Transition table (the SAME machine):
| a | b
---------+--------+--------
->* q_even| q_odd | q_even -> = start
q_odd | q_even | q_odd * = accept state
Trace on input a b a :
q_even --a--> q_odd --b--> q_odd --a--> q_even (in F) => ACCEPT
Trace on input a b b :
q_even --a--> q_odd --b--> q_odd --b--> q_odd (not F) => REJECT上面的轉移表不過是把圖裡的箭頭重新排成一個格子：每個狀態一列、每個符號一欄，格子裡裝著目的地。注意這張表絕不會有空格，也絕不會在一格裡列出兩個狀態——若是如此，δ 就不再是函數，機器也就不再是 DFA。圖對人類比較友善；表對必須儲存這台機器的電腦比較友善。它們可以互換，好的習慣是畫出其中一個、再拿另一個來對照檢查。
讓機器運行：從一步到整個字串
單一個 δ 步驟讀一個符號。要處理一整個字串，你只要一次又一次地重複，從左到右把符號餵進去，且絕不回頭。這就是 DFA 在輸入上的運行，而它徹底是機械式的——沒有任何決定要做，因為 δ 早已把一切決定好了。從 q0 出發，讀第一個符號、沿著那唯一的箭頭走，從你落腳的狀態讀下一個符號、沿著那箭頭走，如此繼續直到字串用盡。
- 把目前狀態設為起始狀態 q0，並把一根「閱讀手指」放在輸入的最左邊符號上。
- 讀出手指下的符號，稱它為 a；把目前狀態換成 delta(目前狀態, a)。永遠恰好有一支箭頭適用——這正是「確定性」在盡它的本分。
- 把手指往右滑過一個符號，並重複前一個步驟。
- 當手指滑出最右端（字串結束）時，停下來，看看你現在所處的狀態。
- 若那個最終狀態是接受狀態（屬於 F），機器就接受這個字串；否則就拒絕。「是／否」只取決於你停在哪裡，從不取決於你走過的路徑。
空字串 ε 值得一句仔細的話。運行 ε 意味著你一個符號都不讀，所以你從不移動——這趟運行從 q0 開始、也在 q0 結束。因此，一台 DFA 接受 ε，當且僅當它的起始狀態 q0 恰好同時也是接受狀態。在我們「偶數個 a」的機器裡，q0 = q_even 是接受狀態，所以 ε 被接受：零個 a 是偶數個 a，這完全正確。理論家用擴展轉移函數（通常在上頭加個帽子）來捕捉「讀完整個字串 w 之後運行停在哪裡」這件事，但你在上面的步驟裡早就在親手計算它了。
死路：陷阱狀態與完整的接線
因為 δ 必須對每一個「狀態與符號」的配對都給出答案，DFA 是完整接線的——絕不會有缺漏的箭頭讓你跌穿過去。初學者常畫出一張半成品的圖，圖裡某個符號在某個狀態下根本沒有出去的箭頭，然後納悶當那個符號到來時會發生什麼。在真正的 DFA 裡那不可能發生；接線是完整的，這個性質有時被明確稱為完全轉移函數。當你想要的語言確實在看到某個壞東西之後就禁止某個符號時，你不是去刪掉一支箭頭——而是把它導向一個特殊的狀態，叫做陷阱狀態（也叫死狀態）。
陷阱狀態就像一間「蟑螂旅館」：一旦你住進去，就再也退不了房。從陷阱出發的每一個符號都直接繞回陷阱本身，而陷阱不是接受狀態。所以當輸入做了某件致命的事的那一刻，你就掉進陷阱，無論後面接什麼都注定拒絕。想像一台處理「不含子字串 aa 的字串」的機器。當你連續讀到第二個 a 的那一刻，未來任何符號都再也救不回來——所以你把那個轉移送進陷阱，讓它把剩下的輸入全部吸收掉。陷阱就是 DFA 用來說「我已經決定『否』了，但我在合約上有義務繼續讀下去」的方式。
接受，以及 DFA 的語言
現在我們可以乾淨俐落地說出「一台 DFA 完成它的工作」是什麼意思。當運行 w 結束於一個接受狀態時，DFA 就接受字串 w，否則拒絕——這條唯一的規則就是接受。現在把這台機器接受的每一個字串都收進一個集合。那個集合就是DFA 的語言，對機器 M 寫作 L(M)。它是 Σ* 的一個子集——正是基礎那一階從字串宇宙裡雕刻出來的那種形式語言。機器與它的語言是同一件事的兩種觀點：造好機器，你就隱含地描述了它的語言；描述語言，你就隱含地在要求一台機器。
凡是某台 DFA 所接受的語言，都贏得了這整一階裡最重要的名字：它被稱為正規語言。這正是建造 DFA 的全部用意——DFA 不是目的，它們是某一類語言的定義。還有一個要帶著往前走的警告，因為它幾乎絆倒每一個人：正規不等於有限。我們「偶數個 a」的語言包含無限多個字串（b、abab、aa、bbaa，如此沒完沒了），但它仍是正規的，因為一台小小的 2 狀態機器就能識別它。大小與正規性完全是不同的兩個面向；一個語言可以是無限的，卻仍然名列機器能識別的最簡單事物之中。
設計小機器——以及一道牆
下一篇導覽要操練的技能是「設計」：從一句英文描述出發，最後得到一台 DFA。訣竅是反問：「為了決定答案，我最少必須記住什麼？」——然後就讓那「最少」恰好成為狀態。對「偶數個 a」而言，唯一值得記住的是奇偶性，所以兩個狀態就夠。對「a 的個數是 3 的倍數」而言，你記住「個數對 3 取餘數」，於是得到三個狀態 q0、q1、q2 排成一個小迴圈。對「含有子字串 ab」而言，你記住目前已經比對到樣式 ab 的多少。每一個設計，都不過是對那個關於「記憶」的問題的一個仔細回答。
兩個設計常常想同時成立——比方說，「偶數個 a 而且 b 的個數是 3 的倍數」。你不必耍聰明：把兩台機器並排運行，讓每個狀態記住一個配對（a 的奇偶性、b 的個數對 3 取餘）。這給出 2 乘 3 = 6 個合併後的狀態，而且永遠行得通。這個把戲有個名字，叫乘積構造，它就是這一階第 4 篇導覽的全部內容——現在只要注意：兩個有限的記憶合併成一個有限的記憶，所以結果仍然是一台 DFA。
但有一道牆，而它是這一階將教給你的最誠實的事：DFA 無法無上限地計數。它的記憶就是那個有限集合 Q，在它見到任何輸入之前就已固定。叫它去識別 a^n b^n——n 個 a 後面接剛好 n 個 b，對每一個 n 都成立——它就必須以某種方式記住有多少個 a 走過去了，而 n 可以是一百萬或十億。假設只有 100 個狀態，兩個不同的「a 計數」最終必定落進同一個狀態（這就是你日後會磨利成幫浦引理的鴿籠想法），在那之後機器就再也分不出那些計數。這個有限記憶極限不是聰明才智的失敗；沒有任何一台 DFA 做得到。正是這一道牆，使得這條階梯繼續向上——通往一台加了堆疊、終於能夠計數的機器。這一階的最後一篇導覽，全部用來誠實地凝視這道牆。