有限狀態機（finite state machine）
/ FY-nyt /
有限狀態機是硬體控制器的標準樣式：一個電路，它總是恰好處於一小組固定狀態中的某一個，並依輸入在它們之間移動。想想一台自動販賣機，從「閒置」到「已投幣」到「出貨」再回到「閒置」——任何一刻它都待在一個具名狀態，而每一枚硬幣或一次按鍵都觸發一次轉移到下一個狀態。有限狀態機把隨時間展開的行為，捕捉成一張由狀態（圓圈）和轉移（圓圈之間的箭頭）構成的整齊圖，這正是工程師描述與建造「為機器動作排序的控制邏輯」的方式。
在硬體裡，有限狀態機有三部分。一個狀態暫存器（一排正反器）握住當前狀態。一塊組合邏輯——下一狀態邏輯——看著當前狀態與輸入，算出下一個時脈邊緣要移到哪個狀態。另一塊——輸出邏輯——產生機器的輸出。有兩種型態：在 Moore 機裡，輸出只取決於當前狀態（更穩、時序更好處理）；在 Mealy 機裡，輸出還取決於輸入（能早一個週期反應、狀態更少）。每個時脈跳動，下一狀態邏輯穩定下來，邊緣把選定的下一狀態載入暫存器——然後循環重複。
它為何重要：有限狀態機是控制器樣式，是告訴資料路徑「做什麼、何時做」的大腦。處理器的控制單元本質上就是一個（或數個）有限狀態機，它讓一條指令逐步走過提取、解碼、執行等等，在每個狀態拉起正確的控制訊號。紅綠燈、通訊協定、電梯控制器，以及記憶體與輸入輸出內部的交握，全都是有限狀態機。「有限」是它誠實的核心：因為狀態只有有限多個，整個行為都可列舉、可驗證——但這也意味著有限狀態機無法無上限地計數、或記住無限長的歷史；那需要在狀態暫存器之外再加儲存。
一個旋轉門有限狀態機有兩個狀態：上鎖與解鎖。從上鎖，投入一枚硬幣轉移到解鎖；從解鎖，推過去轉移回上鎖。在解鎖時投幣、或在上鎖時推，都不改變什麼。兩個狀態、四個箭頭——而那張小圖就是這個控制器一份完整、可建造的規格。
狀態與轉移：有限狀態機是控制器的大腦，而處理器的控制單元就是其中之一。
「有限」這個詞是真正的限制，不是裝飾。有限狀態機有固定數量的狀態，所以它本身無法無上限地計數或記憶——要處理任意大的計數，你必須在狀態暫存器之外再加一個暫存器或記憶體；單靠控制結構是不夠的。