Finite state machines (FSMs)

有限狀態機 (FSM) 簡介

歡迎來到電腦科學中最合乎邏輯且令人滿足的部分！你有沒有想過自動販賣機是怎麼知道你投的錢足夠了？或者簡單的交通燈是怎麼知道何時該變換燈號的呢？它們運作的基礎就是有限狀態機 (Finite State Machine, FSM)。

在這一章，我們將學習如何根據輸入來模擬從一個「狀態」轉換到另一個「狀態」的系統。如果一開始聽起來有點技術性，別擔心——它本質上就是一張展示系統運作方式的地圖！讀完這些筆記後，你將能夠繪製這些地圖，甚至利用它們來設計簡單的電腦邏輯。

什麼是有限狀態機？

從核心本質來看，FSM 是一種運算的數學模型。這是一個在任何特定時間點，都只能處於有限數量之狀態中其中一個的系統。

類比：電燈開關
想像一個普通的電燈開關。它擁有「有限」數量的狀態：它不是開 (ON) 就是關 (OFF)。它不可能同時處於兩者之間，也不可能處於兩者中間的狀態。當你撥動開關（即輸入）時，狀態就會改變。如果是關，它就會變開；如果是開，它就會變關。

FSM 的關鍵組成部分

要了解 FSM，你需要知道以下四點：
1. 狀態 (States)： 機器可能處於的不同狀況（通常以圓圈表示）。
2. 輸入 (Inputs)： 導致狀態變化的事件或觸發因素。
3. 轉換 (Transitions)： 從一個狀態移動到另一個狀態的過程（以箭頭表示）。
4. 輸出 (Outputs)： 機器產生的結果（僅在特定類型的 FSM 中存在）。

快速複習： FSM 就像是簡單機器的一個「大腦」。它記得自己身處何處（狀態），並等待推動力（輸入）來移動到別處。

狀態轉換圖 (State Transition Diagrams)

狀態轉換圖是我們繪製 FSM 的視覺化方式，看起來就像是一組由箭頭連接的圓圈。

如何閱讀圖表：

• 圓圈： 每個圓圈代表一個狀態。狀態名稱通常寫在圈內。
• 起始箭頭： 一個從「虛無」指向某個圓圈的箭頭，標示了初始狀態 (Initial State)（即起點）。
• 箭頭： 這些是轉換。它們顯示機器在接收輸入時的移動方向。觸發該移動的輸入會寫在箭頭上。
• 雙圓圈： 帶有雙邊框的圓圈是接受狀態 (Accepting State)（或結束狀態）。這意味著機器已成功完成其任務。

範例：一個簡單的 FSM，用於檢查二進位字串是否以 '1' 開頭。
1. 從 狀態 S0（初始狀態）開始。
2. 如果輸入是 '1'，則沿著箭頭移動到 狀態 S1（接受狀態）。
3. 如果輸入是 '0'，則沿著箭頭移動到 狀態 S2（拒絕狀態）。

常見錯誤： 忘記標記箭頭！沒有標籤的話，我們就不知道哪個輸入會導致什麼變化。

狀態轉換表 (State Transition Tables)

有時，如果狀態太多，圖表可能會變得混亂。在這種情況下，我們會使用狀態轉換表。這只是一個網格，它以文字格式提供了與圖表完全相同的資訊。

表格結構：
• 左側欄位列出當前狀態 (Current State)。
• 頂部列出所有可能的輸入 (Inputs)。
• 中間的儲存格則告訴你下一個狀態 (Next State)。

範例表格：
當前狀態 | 輸入：0 | 輸入：1
S0 | S0 | S1
S1 | S0 | S1

在此表中，如果你處於狀態 S0 並收到 1，你就會轉移到 S1。

關鍵要點： 圖表非常適合觀察「流程」，而表格則適合用來確保你沒有遺漏每個狀態下任何可能的輸入！

帶輸出的 FSM：米利機 (Mealy Machines)

我們目前討論的 FSM 只是簡單地「接受」或「拒絕」一個序列。然而，牛津 AQA 學生也需要了解米利機 (Mealy Machines)。這些 FSM 會根據當前狀態和輸入產生輸出。

在米利機圖表中，箭頭標記為 輸入 / 輸出。

範例：自動販賣機
想像一台需要存入 20 分錢的機器。
• 狀態：0 分。輸入：10 分。轉換：移動到「10 分」狀態。輸出：「顯示 10」。
• 狀態：10 分。輸入：10 分。轉換：移動到「就緒」狀態。輸出：「釋出飲料」。

數學註記： 輸出由轉換決定。我們將其寫作 \( 輸入 / 輸出 \)。

你知道嗎？ 米利機以 George H. Mealy 的名字命名，他是貝爾實驗室 (Bell Labs) 的先驅，協助開發了早期電信系統的這些概念！

總結與成功秘訣

建立 FSM 的步驟：

1. 識別狀態： 系統可能處於哪些不同的「狀況」？
2. 識別輸入： 什麼會發生並改變這些狀況？
3. 繪製轉換： 對於每一個狀態，決定當每一個可能的輸入發生時會發生什麼。
4. 定義開始/結束： 清晰標示流程從哪裡開始，以及在哪裡成功結束。

記憶法：S.I.T. 規則

為了保持簡單，記住 S.I.T.：
S (State) - 狀態（我現在在哪裡？）
I (Input) - 輸入（剛發生了什麼事？）
T (Transition) - 轉換（我現在要去哪裡？）

最終快速複習：

• 有限 (Finite)： 狀態數量是有限的。
• 確定性 (Deterministic)： 在你學習的 FSM 中，對於任何狀態和輸入，都有且只有一個下一個狀態。
• 狀態轉換圖： 視覺化的地圖（圓圈和箭頭）。
• 狀態轉換表： 地圖的網格版本。
• 米利機： 對每個轉換都會給出輸出的 FSM。

如果一開始覺得很棘手，別擔心！試著為簡單的東西畫一個 FSM，例如微波爐（狀態：閒置、加熱中、暫停）。一旦你能視覺化狀態之間的移動，這些圖表就會變得像直覺一樣簡單！