一台全部記憶就只是一個狀態的機器
從前面幾階你已經知道：正規語言是喬姆斯基階層上的第一族，是字母表 Σ 上最簡單的那類字串模式。現在我們要認識的，正是恰好辨認這些模式的機器。想像地鐵的旋轉柵門：此刻它上鎖，你投入一枚硬幣它就解鎖，你走過去它又重新上鎖。它不記得昨天有多少人經過，也不記得它一共吞過幾枚硬幣——在任一瞬間，它所知道的一切都濃縮成一個詞：上鎖或解鎖。這個唯一的詞就是它的狀態（state），而一台全部記憶就只是「取自一張固定有限清單的一個狀態」的裝置，就叫做有限狀態機。
有限狀態機一次讀一個符號、嚴格由左到右地讀入輸入；每讀完一個符號，它就恰好處於某一個狀態。從一個符號帶到下一個符號的，只有「現在在哪個狀態」這件事——沒有便條紙、沒有計數器、旁邊也沒有額外的儲存空間。一條規則規定：在目前狀態下讀到剛才那個符號，該移到哪個狀態。紅綠燈在綠、黃、紅之間循環，自動販賣機記著目前已投入多少錢，都是日常生活中的有限狀態機。
把它講精確：DFA 五元組
這一階的具體有限狀態機，就是確定型有限自動機，簡稱 DFA。「確定型」（deterministic）這個詞是一句承諾：永遠沒有選擇。給定你在哪裡、剛讀到什麼，下一個狀態就被完全固定——把同一台機器在同一個輸入上跑一千遍，你每次描出的都是同一條路徑。要在不畫圖的情況下把 DFA 釘死，我們把它打包成一個五元組 M = (Q, Σ, δ, q0, F)，也就是這台機器完整的食譜卡。
依序讀出這五樣材料：Q 是有限的狀態集合（圖中的圓圈）。Σ（大寫 sigma）是輸入字母表，也就是機器可讀入的有限符號集合。δ（希臘字母 delta）是轉移函數：它吃進一個狀態與一個符號，回傳恰好一個下一狀態，寫成 delta(q, a) = p，意思是「在狀態 q 讀到符號 a，就走到狀態 p」。q0 是起始狀態，每次執行都從這裡開始。F（Q 的一個子集）是接受狀態的集合，畫成雙圓圈，代表「若你在此結束，答案就是是」。這就是整台機器——再也沒有需要猜測的地方。
這個型別簽名裡藏著兩個安靜的條件，兩者合起來拼出 DFA 裡那個「D」。確定型：delta 回傳單一狀態，絕不是一個集合、也不是一個選擇。全函數（total）：delta 對每個狀態與每個符號都有定義，所以機器永遠不會卡住、不知如何是好。在一台正確的 DFA 裡，每個狀態對每個字母表符號都恰好有一支離開的箭頭——它的表格每一格都恰好填著一個條目。
兩種畫法，一種跑法
同一台 DFA 可以用兩種方式呈現。狀態圖是圖像：每個狀態是一個圓圈，每個轉移是一支帶標籤的箭頭，起始狀態有一支來自虛無、指進去的散箭頭，每個接受狀態是一個雙圓圈。轉移表則是試算表：每個狀態一列、每個符號一欄，列 q 與欄 a 相交的那一格放著 delta(q, a)。它們是同一個物件的兩種視角——每一支從 q 指向 p、標籤為 a 的箭頭，恰恰就是等式 delta(q, a) = p。
執行一個字串，是一趟單一而溫馴的行走。把手指放在起始圓圈上。對每個輸入符號，沿著「從目前圓圈離開、標籤為該符號」的那唯一一支箭頭走（恰好只有一支，因為 delta 是全函數且確定型）。輸入讀完時，看你的手指停在哪：雙圓圈就接受，否則就拒絕。這就是一次計算（run），它有兩個可愛的性質——它是唯一的（沒有要探索的分岔），而且長度恰好等於輸入（n 個符號花 n 步，只用「記住一個狀態」的記憶量）。下面是一台接受「以 1 結尾」之二進位字串的小機器，並在輸入 1101 上執行。
DFA "ends in 1" alphabet {0,1} start: A accept: { B }
transition table state diagram (-> marks start, (( )) = accept)
state | 0 | 1 0 1
----- | - | - +------+ -----1---> (( B ))
-> A | A | B ->| A |<----0------ || B ||
B | A | B +------+
run on 1101 (one path, length 4):
A --1--> B --1--> B --0--> A --1--> B end state B is in F => ACCEPT
run on 1100:
A --1--> B --1--> B --0--> A --0--> A end state A not in F => REJECT關於接受，有兩點誠實的提醒。其一，只有「最終」狀態算數：途中經過某個接受狀態什麼都不代表，真正算數的是輸入用完時你所站的位置。其二，DFA 從不當機——因為 delta 是全函數，每個字串都得到一個乾淨的裁決，而拒絕是個刻意的、良好定義的結果，不是錯誤。
設計 DFA：挑對要記住的事實
DFA 設計的全部藝術就在這裡：每個狀態都應恰好代表關於「目前讀過的輸入」的一項事實（或一組事實的組合）——而狀態集合應該涵蓋你將會用到的每一項事實，不多不少。然後，恰好當你在意的那項事實在最後為真時，你就接受該字串。我們來替字母表 Σ = {a, b} 上的語言「含偶數個 a 的字串」設計一台 DFA。唯一要緊的事實，就是 a 的個數的奇偶：是偶數還是奇數？這是兩種情境，所以兩個狀態，叫 Even 與 Odd。
- 選定起始狀態。在讀任何符號之前，已看到零個 a，而零是偶數——所以從 Even 開始。（把這個基底情形弄對，和把轉移弄對一樣重要；空字串 epsilon 必須落到它該去的地方。）
- 寫下轉移。讀 b 從不改變 a 的個數，所以 b 在兩個狀態上都是自迴圈：delta(Even, b) = Even 且 delta(Odd, b) = Odd。讀 a 則翻轉奇偶：delta(Even, a) = Odd 且 delta(Odd, a) = Even。
- 選定接受狀態。我們要的是「最後個數為偶」，所以 F = { Even }。由於起始狀態 Even 同時也是接受狀態，機器便正確地接受 epsilon（零個 a 是偶數）。完成：四條轉移就完整指定了一台兩狀態的 DFA。
同一套配方可以放大。對「二進位數值可被 3 整除」，就記住「目前數值除以 3 的餘數」——三個狀態 r0、r1、r2，接受 r0；這就是用恰好 k 個狀態做「模 k 計數」。對「含有子字串 ab」，就讓狀態追蹤「你目前已匹配到這個模式的多少」（什麼都還沒看到、剛看到一個 a、看到了 ab），並讓最後那個變成一個你永不離開的陷阱。注意這個訣竅：每一種情形裡，你追蹤的都是一份「對過往的小而有界的摘要」，而從不是原始輸入本身。
死狀態、DFA 的語言，以及那唯一的硬性極限
有時一個字串會以無法挽回的方式出錯——比方說你正在匹配一個固定模式，卻讀到一個把它永遠毀掉的符號。為了讓 delta 保持全函數，你把這類輸入送進一個陷阱狀態（也叫死狀態，dead state）：一個非接受的狀態，它的每一支箭頭都繞回自己。一旦掉進去，你就再也爬不出來，這個字串注定被拒。陷阱狀態不是 bug；它是「這個輸入已經失敗了」這句話誠實而完整的講法，並讓表格的每一格都保持填滿。
執行一台 DFA，一次只判定一個字串。把機器 M 所接受的「所有」字串蒐集進一個集合，你就得到 DFA 的語言，記作 L(M)——也就是「其唯一計算以落在 F 之內作結」的每一個字串所成的集合。一個語言被稱為正規的，恰好當「存在某台 DFA 辨認它」時。這正是喬姆斯基階層第一階的精確含義，也是該守住的那副眼鏡：這門學科裡後面每一台機器，骨子裡都是對「它能辨認哪一族語言？」這個問題的不同回答。
現在來到本階最深的單一課題：有限記憶極限。因為 Q 是有限的，DFA 只能區分有限多種情境。它能記住上一個符號、一個奇偶、一個模 k 的餘數、或自己沿著一個固定模式走到哪——但它無法記住一個「無上界」的累加計數。試著替 a^n b^n（n 個 a 後面恰接 n 個 b，對任意 n）造一台 DFA：要檢查 b 的個數相符，你得記住前面來了幾個 a，而那個數沒有上限。只有 k 個狀態時，兩個不同的 a-個數終究會落進同一個狀態，從那一刻起機器就再也分不出它們。DFA 就是無法「無上界地計數」。
這不是不夠聰明的失敗；它是一道可被證明的牆，而往後的幫浦引理（喬裝過的鴿籠原理）會讓我們嚴格地證明它。這道牆也正是攀登得以繼續的理由：為了能無上界地計數，我們會在下推自動機裡遞給機器一疊盤子，那是沿著階層往上的下一個大步。此刻，你已經能讀懂 DFA、執行它、替子字串、奇偶與模 k 計數設計它，並能說出它那唯一真正的極限。