Finite state machines (FSMs)

理解有限狀態機 (Finite State Machines, FSMs)

你好！歡迎來到計算理論 (Theory of Computation) 單元。計算機科學的這個領域旨在探討哪些問題可以通過電腦解決，以及我們如何對這些過程進行建模。如果聽起來很抽象，別擔心——我們將從最簡單、最容易理解的計算模型開始：有限狀態機 (FSM)。

無論你是否意識到，你每天都在與 FSM 打交道！從交通燈到密碼驗證，它們是簡單系統運作方式的數學基礎。

什麼是有限狀態機 (FSM)？

有限狀態機 (Finite State Machine, FSM)，有時也稱為有限自動機 (Finite Automaton, FA)，是一種數學模型，用於設計只有有限且固定數量的操作條件（即「狀態」）的系統。

類比：想像一個交通燈。它只能處於三種狀態之一：紅燈、紅黃燈或綠燈。它不能同時處於紅燈和綠燈狀態。這些狀態之間的轉換由輸入（例如計時器）觸發。

FSM 的核心組件

一個 FSM 有四個主要的必要組件：

• 狀態 (States)： 機器可能處於的一組有限的條件或配置。
• 開始狀態 (Start State)： 機器開始運作時的初始狀態。
• 輸入字母表 (Input Alphabet)： 機器可以接收的一組有限符號（或事件）。這些符號會觸發狀態之間的移動。
• 轉換 (Transitions)： 指定機器如何根據接收到的輸入從一個狀態移動到另一個狀態的規則。

重點小結： FSM 是由固定、有限數量的狀態以及狀態間移動規則所定義的簡單機器。它們是無記憶的（它們只關心當前狀態和當前輸入）。

表示有限狀態機

我們有兩種主要的正式方式來描述 FSM：使用圖表（視覺化）和使用表格（結構化）。你必須能夠繪製並解讀這兩種方式。

1. 狀態轉換圖 (State Transition Diagrams)

這是將 FSM 視覺化最直觀的方法。

• 狀態畫為圓圈或節點。
• 開始狀態由一個從虛無指向它的箭頭表示。
• 轉換（狀態之間的移動）畫為連接狀態的箭頭。
• 每個轉換箭頭都標有觸發該移動的輸入符號。
• 如果 FSM 用於識別（例如驗證密碼），我們可能會使用接受/終止狀態 (Accept/Halting States)，通常以雙圓圈表示。

範例：一個檢查輸入字串是否包含兩個連續 '1' 的簡單 FSM。

如果狀態 A 是開始狀態，狀態 C 是接受狀態，從 A 到 B 的箭頭可能標記為 '1'，從 B 到 C 的箭頭也可能標記為 '1'。

2. 狀態轉換表 (State Transition Tables)（正式視角）

狀態轉換表顯示的資訊與圖表相同，但採用了正式的表格格式。這通常更適合用於檢查每一種可能的情況。

• 行通常代表當前狀態 (Current State)。
• 列通常代表輸入符號 (Input Symbol)。
• 表格中的內容指定了下一個狀態 (Next State)。

帶輸出的 FSM：僅限 Mealy 機 (Mealy Machines)

課程大綱要求你理解產生輸出的 FSM。關鍵在於，你只需要了解 Mealy 機。

在 Mealy 機中，輸出是在轉換過程中產生的。

輸出取決於： (當前狀態) AND (接收到的輸入)

記憶輔助： 想想 'M' 代表 Movement（移動）。Mealy 的輸出發生在 **M**ovement（轉換）上。

在 Mealy 圖表或表格上標記轉換時，標籤看起來會像這樣：

輸入 / 輸出

範例轉換： 如果 FSM 處於狀態 S1 並接收到輸入 'a'，它會移動到 S2 並輸出 '0'。
圖表標籤：a / 0

重點小結： FSM 可以通過視覺（圖表）或正式（表格）方式建模。對於帶輸出的機器，記住 Mealy 規則：輸出與特定的輸入/轉換掛鉤。

正規表達式與正規語言

有限狀態機是一種計算模型。正規表達式 (Regular Expressions, REs) 是一種描述這些 FSM 可以識別的字串集（即語言）的方法。它們在程式設計中對於驗證資料、搜尋文字和檢查輸入格式非常有用。

什麼是正規語言？

正規語言 (Regular Language) 是任何可以由正規表達式定義或由 FSM 識別的字串集。

你知道嗎？幾乎所有現代程式語言（Python、Java 等）都使用正規表達式進行模式匹配！

元字元：正規表達式的建構塊

RE 使用特殊符號（元字元）來簡潔地描述模式。你必須熟悉以下符號：

重複與可選性

• * (Kleene 星號)： 匹配前一個元素零次或多次重複。
  • 範例： A* 匹配 "", "A", "AA", "AAA" 等。
  • 記憶輔助： 星號意味著「完全可選，可能重複多次」。
• + (Kleene 加號)： 匹配前一個元素一次或多次重複。
  • 範例： A+ 匹配 "A", "AA", "AAA" 等，但不匹配 ""。
  • 記憶輔助： 加號意味著「至少一次」。
• ? (可選)： 匹配零次或一次重複（前一個元素是可選的）。
  • 範例： Colou?r 同時匹配 "Color"（美式拼法）和 "Colour"（英式拼法）。

分組與選擇

• | (交替或 OR)： 匹配該符號之前的表達式或之後的表達式。
  • 範例： Cat|Dog 匹配字串 "Cat" 或字串 "Dog"。
• () (分組)： 用於將正規表達式組合在一起，以便元字元（如 * 或 +）應用於整個組。
  • 範例： (AB)+ 匹配 "AB", "ABAB", "ABABAB" 等。（如果寫成 AB+，它會匹配 "A" 後面跟著一個或多個 "B"）。

字元類別

字元類別允許你指定可以在特定位置匹配的一組字元。

• 直接選擇： [CH] 匹配字元 'C' 或字元 'H'。
• 範圍選擇： [A-Z] 匹配 A 到 Z 之間（含）的任何單個大寫字母。

常見錯誤： 確保你理解 *（零次或多次）和 +（一次或多次）之間的區別。如果語言要求字元至少出現一次，請使用 +。

重點小結： 正規表達式是強大的模式描述工具。學習元字元（尤其是 *, +, ?, |），因為它們對於定義正規語言至關重要。

FSM 與正規表達式之間的關係

這是本節最重要的理論概念之一：

正規表達式和 FSM 是定義正規語言的等價方法。

這意味著如果你能繪製一個 FSM 來識別某種模式，你就一定能寫出一個正規表達式來描述該模式，反之亦然。

應用等價性

在考試情境中，你可能會被要求在這些模型之間進行轉換：

1. FSM 轉正規表達式 (RE)

你需要追蹤 FSM 中從開始狀態到接受狀態的路徑，並使用元字元來表示迴圈和選擇。

• 任務： 編寫一個 RE 來描述由給定 FSM 識別的語言。
• 範例 FSM： 識別偶數個 '1'（從狀態 S0 開始，輸入 '0' 時停留在 S0，輸入 '1' 時移動到 S1。輸入 '1' 時回到 S0，輸入 '0' 時停留在 S1）。S0 是接受狀態。
• 對應的 RE： (0*10*1)*0*
  • 解釋： 任意數量的 0 (0*)，後面跟著一對由任意數量 0 分隔的 1 (10*1)。整個模式必須重複零次或多次 (...) * 以確保 1 的數量為偶數，最後以任意數量的 0 (0*) 結尾。

2. 正規表達式轉 FSM 設計

你需要設計必要的狀態和轉換，以精確實現 RE 定義的邏輯。

• 任務： 設計一個 FSM 來識別與給定 RE 相同的語言。
• 範例 RE： A(B|C)*（匹配一個 'A'，後面跟著零個或多個 'B' 或 'C' 的序列）。
• FSM 設計步驟：
  1. 建立一個開始狀態 (S0)。
  2. 從 S0 的轉換必須是 'A' 才能到達下一個邏輯狀態 (S1)。
  3. S1 必須處理 (B|C)* 部分。由於這意味著 'B' 或 'C' 出現零次或多次，S1 必須是最終的接受狀態，並且在接收到輸入 'B' 或 'C' 時必須循環回到自身。
  4. 你需要畫箭頭從 S1 回到 S1，標記為 'B' 和 'C'。

意義

這裡的關鍵結論是關於正規性原則 (Regularity Principle) 的知識：

一種語言是正規的 (regular)，當且僅當它能被 FSM 識別。由於 FSM 和 RE 是等價的，這意味著如果你看到一個 RE，你就知道一個簡單的 FSM 可以處理它。

重點小結： FSM 和正規表達式是可以互換的。它們定義了相同類別的簡單語言——正規語言。你必須練習在這兩種形式之間進行轉換。