一、全世界最小的一台
牆上的電燈開關。
它只有兩種情況:燈亮著,或燈暗著。你能做的動作只有一個:按一下。
┌──── 按一下 ────┐
│ ▼
[ 暗 ] [ 亮 ]
▲ │
└──── 按一下 ────┘
這就是一台狀態機,而且大概是最小的一台。
它小到看起來沒什麼好講的,但裡面藏著整件事的核心:同樣是「按一下」這個動作,結果不一樣,因為開關記得自己現在在哪。
燈亮的時候按一下,燈滅。燈暗的時候按一下,燈亮。動作完全相同,結果相反。差別只在於它「現在」在什麼情況。
一台機器如果會因為「自己現在在哪個情況」而對同一個動作做出不同反應,它就是狀態機。
二、加幾個情況:洗衣機
兩種情況太少,看不出用處。換一台洗衣機。
[ 待機 ] ──按啟動──▶ [ 洗滌中 ] ──洗完──▶ [ 脫水中 ]
▲ │
│ 脫完
│ ▼
└────────── 開門拿衣服 ────────── [ 完成 ]
現在有四種情況,而且讓它改變的動作變多了:按啟動、洗完、脫完、開門。
這台機器有一件事值得注意:不是每個動作在每個情況下都有效。
洗衣機在脫水的時候,你按開門是沒用的,門鎖著。這是刻意設計的。脫水時滾筒每分鐘轉上千圈,門如果能打開會出人命。
所以「脫水中」這個情況,沒有一條叫「開門」的箭頭連出去。
這句話請記住,它是後面所有東西的關鍵。
三、四個名字
你剛剛已經看懂兩台狀態機了,現在才給它們的零件取名字,一共四個。
狀態。機器當下所處的情況。暗、亮、待機、洗滌中,這些都是狀態。狀態的數量必須是有限的、數得出來的,這是這整套東西能運作的前提。
事件。讓狀態改變的那個動作。按一下、按啟動、洗完、開門。有些事件是人做的,有些是機器自己完成某件事之後發出的。
轉換。「在某個狀態、發生某個事件、就跑到另一個狀態」這整件事。上面圖裡的每一支箭頭都是一個轉換。
狀態圖。就是上面那種圖。通常圈圈是狀態,箭頭是事件。
只有這四個。接下來不會再有新名詞,除了一個學名,那個放到後面講。
四、真正的用處在「畫不出來的箭頭」
多數人第一次看到狀態圖,會覺得它就是流程圖的親戚,用來描述「事情會怎麼走」。
它真正的價值在相反的地方:描述事情不會怎麼走。
拿網購訂單來看。一筆訂單大概會經過這些狀態:

把圖畫出來之後,真正的工作才開始:檢查每一對狀態之間,箭頭該不該存在。
已送達能不能退款,這是商業決策,公司要自己決定。 已取消能不能再付款,大概不行,要重下一筆。 已退款能不能跳回運送中,絕對不行。
那些你決定「不行」的,就不要畫箭頭。
圖上的空白跟畫出來的線一樣重要。沒有箭頭的地方,等於告訴系統:這個操作要擋下來。
很多很嚴重的 bug,本質上就是圖上該空著的地方被連了線:
訂單已經取消,扣款還是照常執行。 付款頁面按兩次送出,變成兩筆訂單。 退款已經完成,倉庫又出了一次貨。
這三種事故在新聞上都出現過,每一個都是「系統允許了一個不該存在的狀態轉換」。
把狀態圖畫在紙上,這類問題在寫任何一行程式之前就會被看見。這是它最值錢的地方。
五、那個學名
你剛剛畫的東西,在學術上有個名字叫 DFA。
這三個字母是 Deterministic Finite Automaton 的縮寫,中文翻成確定有限狀態自動機。名字嚇人,拆開來看每個字都在講你已經知道的事。
確定性。在同一個狀態、遇到同一個事件,一定跑到同一個地方。燈暗的時候按一下,永遠是變亮,不會今天變亮明天變成別的。
有限。狀態的數量是有限的、數得完的。四個、七個、三十個都可以,重點是數得出來。
自動機。這類機器的統稱,就是個學名而已。
所以 DFA 就是「情況數量有限、而且反應固定」的機器。你家的電燈開關是一台 DFA,洗衣機是一台 DFA,訂單系統也是。
資工系會花好幾週教這個,考試要你畫圖、證明某些東西畫不出來。那些是數學訓練。對大部分人來說,知道「這個嚇人的縮寫講的就是剛才那張圖」就夠了。
六、它做不到的事
有限狀態機有一個很硬的限制:它不會數數。
它知道自己在哪個狀態,但記不住「我經過這裡幾次了」。
舉個會卡住它的例子。檢查一串括號有沒有配對:
(()) 正確
(() 錯誤,少一個
())( 錯誤,順序不對
要判斷這個,機器必須記住「目前開了幾層還沒關」。可能開一層,可能開一百層,沒有上限。既然沒有上限,就沒辦法用有限個狀態去對應。
這件事在編譯器裡有個很清楚的分界。
編譯器讀你的程式碼,第一步是把一長串字元切成有意義的單位:這是關鍵字、這是數字、這是字串。這一步用狀態機就夠了,因為它只需要知道「我現在在字串裡面嗎」「我現在在註解裡面嗎」,不需要記得經過幾次。
第二步要判斷語法結構,括號、大括號、巢狀的區塊,這就需要數數了。所以這一步得外掛一個東西幫它記,像是一疊可以往上堆、往下拿的盤子。
這條界線很乾淨:需要記住數量的事,有限狀態機做不到。
七、正規表示式是哪來的
一段很短的來歷,不想看可以跳過,不影響前面任何一節。
1940 年代,科學家為了描述神經元網路怎麼運作,寫下了「一堆開關、每個開關下一刻的狀態由這一刻決定」的模型。
1951 年,數學家 Stephen Kleene 想回答一個問題:這種機器到底認得出什麼東西?為了寫下答案,他發明了一套記號。
那套記號就是今天的正規表示式。
這點值得停一下。如果你用過正規表示式,比如用 \d{4} 去抓四位數字,那你一直在寫的東西,本質上就是一張狀態圖的文字版。兩者完全等價,Kleene 證明過。你寫的每一條 regex,背後都會被轉成一台狀態機去跑。
1968 年,貝爾實驗室的 Ken Thompson 把這套記號做進一個文字編輯器,讓使用者可以搜尋複雜的樣式。那個編輯器有一道指令,意思是「全域搜尋這個樣式然後印出來」,寫作 g/re/p。後來這道指令被拆出來變成獨立程式。
它叫 grep。
八、現在
這幾年狀態機在軟體圈又熱起來,因為有幾個地方特別需要它。
介面。按鈕按下去之後、伺服器還沒回應之前,那段時間使用者再按一次會怎樣?如果沒管理好就是送出兩筆。把按鈕的狀態寫成「可按、送出中、完成、失敗」,送出中就不接受點擊。這跟洗衣機脫水鎖門是完全同一件事。
雲端流程。一件工作分成好幾步,中間某步失敗了要重試幾次、重試還是失敗要往哪走。這些寫成狀態圖,整條流程就看得見。
AI 代理。這是最近的新用途,也最值得講。
大型語言模型的輸出是機率性的。同樣的問題問兩次,它會給你兩個不太一樣的答案。它的長處就是即興發揮。
把這種東西放進要處理錢、庫存、退款的系統裡,你需要一個東西把它框住。
狀態機就是那個框。AI 可以在框裡面自由決定要查哪個資料、怎麼措辭、下一步做什麼,但它沒有辦法把一筆「已退款」的訂單變回「備貨中」,因為那條箭頭根本不存在。
越是讓機器自由發揮的系統,越需要一份「確定有限狀態自動機」。
gemini補充:

