歡迎來到有限狀態機的世界！
在本章中，我們將深入探討計算理論 (Theory of Computation)，重點研究有限狀態機 (Finite State Machines, FSMs)。別被這個名稱嚇到了！其實，FSM 的本質非常簡單，它只是一個「邏輯地圖」，展示了系統如何根據發生的事件，從一個狀態轉換到另一個狀態。
理解 FSM 至關重要，因為它們是電腦處理語言、紅綠燈運作，甚至是電子遊戲中 NPC（非玩家角色）決定下一步行動的基礎。讀完這些筆記後，你就能像專業人士一樣繪製並解讀這些「邏輯地圖」了！
什麼是有限狀態機？
有限狀態機 (Finite State Machine) 是一種計算的數學模型。讓我們拆解這個名稱來理解其實際含義：
1. 有限 (Finite)： 這意味著機器所處的狀態數量是有限且固定的，它不可能有無窮多種選擇。
2. 狀態 (State)： 這是指機器在特定時刻的「情況」或「狀態」。
3. 機器 (Machine)： 一個接收輸入 (Input)，並根據當前狀態決定下一步要移動到哪個狀態的系統。
你知道嗎？ 你的微波爐就是一個簡單的 FSM！它有待機 (Idle)、烹飪 (Cooking) 和 暫停 (Paused) 等狀態。按下「開始」按鈕是一個輸入，它會導致機器從待機轉換 (Transition) 到烹飪狀態。
必須記住的關鍵術語
• 狀態 (State)： 一種特定的情況（例如：「已鎖定」或「已解鎖」）。
• 轉換 (Transition)： 從一個狀態移動到另一個狀態的過程。
• 輸入 (Input)： 觸發轉換的事件（例如：投入硬幣）。
• 起始狀態 (Initial State)： 機器開始運作的起點。
• 接受（終止）狀態 (Accepting/Final State)： 代表「成功」或「有效」結果的狀態。
視覺化 FSM：狀態轉換圖
展示 FSM 最常見的方法是使用狀態轉換圖 (State Transition Diagram)。這是一張使用特定符號繪製的視覺地圖。別擔心，如果一開始覺得困難，只要熟悉了這些符號，讀起來就像閱讀流程圖一樣簡單！
圖表結構解析
• 圓圈： 代表狀態。我們通常會在圓圈內寫上狀態名稱（例如：\(S_0, S_1\)）。
• 箭頭： 代表轉換。它們顯示了機器移動的方向。
• 箭頭標籤： 箭頭上的文字是完成該移動所需的輸入。
• 「起始」箭頭： 一個指向圓圈但沒有起點的箭頭，標識了起始狀態。
• 雙圓圈： 圓圈內還有一個圓圈，代表接受狀態。如果處理完所有輸入後機器停在這裡，則該輸入序列即被接受 (Accepted)。
現實生活中的例子：簡單閘門
想像一個通常處於已鎖定 (Locked) 狀態的安全閘門。
1. 如果你在已鎖定時推它，它會保持已鎖定。
2. 如果你投入一枚硬幣 (Coin)，它會移動到已解鎖 (Unlocked) 狀態。
3. 如果你在已解鎖時推 (Push) 它，它會打開，然後變回已鎖定狀態。
在這個例子中，已鎖定和已解鎖是狀態。硬幣和推則是輸入。
複習小貼士： 記住雙圓圈！這是學生最容易忘記的地方。它告訴我們機器已經達到了一個「有效」的結論。無輸出的 FSM
在 AQA AS Level 的課程大綱中，我們特別關注無輸出的 FSM（也稱為有限狀態自動機）。這些機器的任務很簡單：決定一串符號序列是被接受 (Accepted) 還是拒絕 (Rejected)。
如何追蹤 FSM（分步指南）
要判斷一個序列（如「1101」）是否被接受，請執行以下步驟：
1. 從起始狀態開始（尋找那個沒有起點的箭頭）。
2. 讀取輸入字串的第一個符號。
3. 沿著與該符號匹配的箭頭移動到下一個狀態。
4. 對字串中的每個符號重複此步驟。
5. 檢查最終位置： 當所有符號處理完畢後，如果你停在一個雙圓圈狀態，則該字串被接受。否則，它將被拒絕。
要避免的常見錯誤
「死胡同」陷阱： 有時某個狀態對於特定的輸入沒有對應的轉換（例如：你處於狀態 A，輸入為 '1'，但沒有標記為 '1' 的箭頭）。在許多簡單的 FSM 中，如果沒有有效的移動路徑，機器會「崩潰」，該輸入會立即被拒絕。
關鍵總結： 無輸出的 FSM 就像是「接受檢測器」。它們只關心你最終是否停在正確的位置（雙圓圈）。狀態轉換表
有時，如果狀態太多，繪製圖表會變得很混亂。這時就需要狀態轉換表 (State Transition Table)。它包含完全相同的資訊，只是以網格形式呈現！
如何閱讀/建立表格
• 橫列 (Rows) 代表當前狀態。
• 直欄 (Columns) 代表接收到的輸入。
• 儲存格 (Cells) 告訴你下一個狀態。
例如，表格看起來像這樣：
當前狀態 | 輸入: 0 | 輸入: 1
------------------------------------
S0 (起始) | S0 | S1
S1 (終止) | S0 | S1
這張表告訴我們：「如果你處於 S0 並收到 1，請移至 S1。」
記憶法： 「如果-而且-那麼」規則
要記住如何使用表格，只需說：「如果 (IF) 我處於這個狀態，而且 (AND) 我得到這個輸入，那麼 (THEN) 我就移動到那個狀態。」
計算理論總結：FSM
• FSM 是具有有限數量狀態的系統模型。
• 轉換由輸入觸發。
• 狀態轉換圖是視覺地圖；狀態轉換表是網格。
• 起始狀態 = 沒有起點的箭頭。接受狀態 = 雙圓圈。
• 對於無輸出的 FSM，機器只有在結束於接受狀態時才會接受字串。
如果覺得這些概念很抽象，不用擔心！掌握 FSM 的最好方法就是練習為簡單的任務繪製它們，例如建立一個只接受以 '1' 結尾的二進位數字的機器。你一定做得到的！