有限狀態機 — 計算理論

什麼是有限狀態機？

有限狀態機（Finite State Machine，FSM）又稱有限狀態自動機，是計算理論中最基本的計算模型之一。它用於描述一個系統在有限數量的狀態之間進行轉換的行為，根據輸入字元從一個狀態轉移到另一個狀態。有限狀態機在電腦科學的許多領域都有廣泛應用，包括編譯器的詞彙分析、協定設計、數位電路設計、遊戲 AI 等。

形式定義

有限狀態機是一個五元組 M = (Q, Σ, δ, q₀, F)：

Q  - 有限的非空狀態集合 (States)
Σ  - 有限的輸入字母表 (Alphabet)
δ  - 轉移函數 (Transition Function): Q × Σ → Q
q₀ - 起始狀態 (Initial State), q₀ ∈ Q
F  - 接受狀態集合 (Final States), F ⊆ Q

根據轉移函數的不同特性，分為兩種主要類型：

確定型 (DFA)：轉移函數 δ(q, a) 至多返回一個狀態
非確定型 (NFA)：轉移函數 δ(q, a) 可以返回多個狀態，允許空轉移 (ε-轉移)

DFA 與 NFA 的比較

特性	DFA	NFA
轉移確定性	每個狀態每個輸入只有一個轉移	可能有多個轉移
ε-轉移	無	有
記憶體需求	O(1)	可能需要指數空間
設計難度	較高	較低
等價性	與 NFA 等價	與 DFA 等價

等價性定理：對於任何 NFA，存在一個等價的 DFA 接受相同的語言。證明使用子集構造法：DFA 的每個狀態對應 NFA 狀態集合的一個子集。

範例：識別以 01 結尾的二進位字串

設計一個 DFA 來識別所有以 "01" 結尾的二進位字串：

狀態 q0：起始狀態，還沒看到有效的結尾
狀態 q1：剛讀到 '0'
狀態 q2：已讀到 "01"（接受狀態）

轉移函數：
- δ(q0, 0) = q1, δ(q0, 1) = q0
- δ(q1, 0) = q1, δ(q1, 1) = q2
- δ(q2, 0) = q1, δ(q2, 1) = q2

這個 DFA 會接受 "01", "001", "101", "0101" 等，拒絕 "0", "1", "10", "100" 等。

有限狀態機的極小化

兩個狀態稱為等價，如果從其中一個狀態出發讀取任何字串到達的都是接受/拒絕狀態，從另一個狀態出發也一樣。Myhill-Nerode 定理提供了判斷兩個狀態是否等價的框架：語言 L 是正則的當且僅當 L 的 Myhill-Nerode 等價類的數量是有限的。

本課程範例

finiteStateMachine/finiteStateMachine.py — FSM 模擬器
finiteStateMachine/even0.py — 偶數個 0 的範例
finiteStateMachine/an.py — aⁿ 範例
finiteStateMachine/anbm.py — aⁿbᵐ 範例