4.1 有限狀態機與最小化#

概念說明#

有限狀態機（Finite State Machine, FSM）由五元組 (S, I, O, δ, λ) 構成：狀態集合 S、輸入字母 I、輸出字母 O、轉移函數 δ: S×I→S、輸出函數 λ。Mealy 機的輸出依賴「狀態＋輸入」（λ: S×I→O），Moore 機的輸出只依賴狀態（λ: S→O）。兩者表達力相同，可互相轉換（Moore 轉 Mealy 不增狀態，反向可能增加）。

狀態最小化的目標：合併「行為等價」的狀態。兩狀態 s、t 等價，定義為：對所有輸入序列，從 s 與 t 出發產生的輸出序列完全相同。直接比對所有無限序列不可行，幸好有經典結果——等價關係可用「不動點迭代」逐步逼近：

第 0 步：s ~₀ t 若對每個輸入 a，λ(s,a) = λ(t,a)（單步輸出相同）。
第 k+1 步：s ~ₖ₊₁ t 若 s ~ₖ t 且對每個 a，δ(s,a) ~ₖ δ(t,a)。
迭代到分割不再變化（不動點），即得最粗等價關係——此即 Moore 演算法，至多 |S|−1 輪收斂。

Hopcroft 演算法將此過程加速到 O(n log n)：以「分割細化」為框架，聰明地只處理「可能被分裂的區塊」，用 worklist 避免重掃全部狀態，是自動機理論中最重要的演算法之一。

演算法步驟（Moore 分割細化）#

初始分割 P₀：按「輸出簽章」分組——對每個輸入的輸出值所構成的向量相同的狀態放同一塊。
對每塊 B，檢查其成員的「後繼所在塊」簽章是否一致；不一致者把 B 分裂成數塊。
重複直到 P 不再變化。
每塊選一個代表狀態，重建轉移表，即得最小 FSM。

Python 程式碼範例#

def minimize_fsm(states, inputs, delta, out):
    """
    states: 狀態串列; delta: dict[(s,a)] -> s'; out: dict[(s,a)] -> o
    回傳 (代表狀態映射, 最小化後的轉移表)
    """
    # 步驟1：按輸出簽章初始分組
    sig = lambda s: tuple(out[(s, a)] for a in inputs)
    part = {}
    for s in states:
        part.setdefault(sig(s), []).append(s)
    partition = list(part.values())

    def block_of(s):
        for i, b in enumerate(partition):
            if s in b:
                return i
        return -1

    # 步驟2~3：反覆細化直到不動點
    changed = True
    rounds = 0
    while changed:
        changed = False
        rounds += 1
        new_partition = []
        for blk in partition:
            # 每個成員的「後繼塊簽章」
            groups = {}
            for s in blk:
                key = tuple(block_of(delta[(s, a)]) for a in inputs)
                groups.setdefault(key, []).append(s)
            new_partition.extend(groups.values())
            if len(groups) > 1:
                changed = True
        partition = new_partition
    print(f"收斂於第 {rounds-1} 輪細化, 狀態 {len(states)} -> {len(partition)}")

    # 步驟4：代表狀態重建轉移表
    rep = {s: blk[0] for blk in partition for s in blk}
    new_delta = {(rep[s], a): rep[delta[(s, a)]]
                 for blk in partition for s in blk for a in inputs}
    new_out = {(rep[s], a): out[(s, a)]
               for blk in partition for s in blk for a in inputs}
    return rep, new_delta, new_out

# 範例：序列偵測器含冗餘狀態
states = ['A', 'B', 'C', 'D', 'E']
inputs = [0, 1]
delta = {('A',0):'A', ('A',1):'B',
         ('B',0):'C', ('B',1):'B',
         ('C',0):'A', ('C',1):'D',
         ('D',0):'C', ('D',1):'E',   # D 與 E 對未來輸入行為等價
         ('E',0):'C', ('E',1):'E'}
out =   {('A',0):0, ('A',1):0, ('B',0):0, ('B',1):0,
         ('C',0):0, ('C',1):0, ('D',0):0, ('D',1):1,
         ('E',0):0, ('E',1):1}

rep, nd, no = minimize_fsm(states, inputs, delta, out)
print("代表映射:", rep)
print("最小化轉移表:")
for (s, a) in sorted(nd, key=str):
    print(f"  δ({s},{a}) -> {nd[(s,a)]}, 輸出 {no[(s,a)]}")

輸出：

收斂於第 2 輪細化, 狀態 5 -> 4
代表映射: {'A': 'A', 'B': 'B', 'C': 'C', 'D': 'D', 'E': 'D'}
最小化轉移表:
  δ(A,0) -> A, 輸出 0
  ...

D 與 E 被判定等價合併——無論之後輸入什麼，兩者的輸出序列皆相同，因此硬體上只需 4 個狀態的暫存器。

複雜度分析#

Moore 演算法：每輪 O(|S|²·|I|)，至多 |S| 輪，總 O(|S|³·|I|)。
Hopcroft：O(|S| log |S| · |I|)，但實作較複雜。
判定兩狀態是否等價亦可用「成對表格 + 不動點」O(n²) 完成，適合教學演示。

練習#

手工執行 Moore 細化於題目中 5 狀態機，畫出 P₀ → P₁ → P₂ 的分割演變。
實作 Mealy 轉 Moore 的轉換函式，並驗證轉換後再最小化得到的狀態數。
實作 Hopcroft 演算法的 worklist 結構，在 100 個狀態的隨機 FSM 上比較與 Moore 演算法的執行時間。