歡迎來到正規語言的世界！
你好！今天，我們要深入探討計算理論 (Theory of Computation) 中一個引人入勝的領域：正規語言 (Regular Languages)。別擔心，如果起初覺得有些抽象——你可以將這章節想像成學習電腦用來識別規律的「語法」。無論是自動販賣機判斷你投入的零錢是否足夠，還是搜尋引擎在文件中尋找特定字詞，正規語言都在背後默默運作。讓我們一步步拆解吧！
1. 有限狀態機 (Finite State Machines, FSMs)
在討論語言之前，我們必須先了解負責讀取它們的「機器」。有限狀態機 (FSM) 是一個簡單的計算模型。它具有有限 (finite) 的狀態數量，並根據輸入在這些狀態之間切換。
不帶輸出的 FSM
這些機器就像「是非題」裁判。它們讀取一串符號，最後告訴你這串符號是被接受 (accepted) 還是被拒絕 (rejected)。
• 起始狀態 (Start State)： 由一條從無指向它的箭頭表示。
• 接受狀態 (Accepting State)： 由雙圈表示。如果你最終停在這裡，機器就會「接受」該輸入。
帶輸出的 FSM：米利機 (Mealy Machines)
米利機 (Mealy Machine) 是一種特殊的 FSM，它會為每一次轉換提供輸出。
類比：想像一台自動販賣機。當你投入「一英鎊硬幣」時，機器不僅僅是改變狀態，它可能會「輸出」一則顯示訊息，例如「請選擇飲料」。
表示 FSM 的方法
我們可以用兩種方式展示 FSM 的運作：
1. 狀態轉移圖 (State Transition Diagrams)： 使用圓圈（狀態）和箭頭（轉換）組成的視覺化地圖。
2. 狀態轉移表 (State Transition Tables)： 一個顯示當前狀態、輸入以及下一個狀態將是什麼的表格。
快速複習箱：
• FSM： 擁有固定數量狀態的機器。
• 接受狀態： 終點目標！代表輸入字串是有效的。
• 米利機： 會產生輸出的 FSM。
2. 正規表達式的數學基礎：集合 (Sets)
要理解正規語言，我們需要學習集合的語言。集合只是一組無序的項目組合。
重要的集合記號
• \( A = \{1, 2, 3\} \)： 包含數字 1、2 和 3 的集合。
• \( \emptyset \)： 空集合 (empty set)（內部沒有任何元素的集合）。
• \( x \in \mathbb{N} \)： 這意味著「\( x \) 是自然數集合的成員」（0, 1, 2, 3...）。
• \( | \)： 這個符號意思是「使得 (such that)」。例如，\( \{x | x > 5\} \) 意指「所有 \( x \) 的集合，使得 \( x \) 大於 5」。
集合類型
• 有限集合 (Finite Set)： 你可以數出裡面的元素（例如：班上的學生人數）。
• 無限集合 (Infinite Set)： 數量無窮無盡（例如：所有偶數的集合）。
• 可數無限集合 (Countably Infinite Set)： 一種無限集合，只要你有足夠的時間，理論上可以將元素一個一個「數」出來（例如自然數 \( \mathbb{N} \)）。
集合運算
將這些想成「群體的數學運算」：
• 聯集 (\( \cup \))： 將兩個集合合併。
• 交集 (\( \cap \))： 只找出同時出現在兩個集合中的項目。
• 差集 (\( \backslash \) 或 \( - \))： 取出第一個集合，並減去同時也在第二個集合中的任何元素。
你知道嗎？
笛卡兒積 (Cartesian Product) (\( X \times Y \)) 是一種將一個集合中的每個元素與另一個集合中的每個元素配對的方法。如果集合 X 是 {紅色, 藍色} 而集合 Y 是 {汽車, 單車}，那麼乘積就是 {(紅色, 汽車), (紅色, 單車), (藍色, 汽車), (藍色, 單車)}。
重點總結： 集合是基礎建構塊。只要你知道如何分組項目並使用像 \( \in \)（屬於）和 \( \cup \)（聯集）這樣的符號，你就已經成功了一半！
3. 正規表達式 (Regular Expressions, RegEx)
正規表達式 (RegEx) 是描述字串集合的一種簡寫方式。我們不需要列出所有可能的有效字串，而是使用一種模式 (pattern) 來表示。
元字元 (你的 RegEx 工具箱)
• \( * \) (Kleene 星號)： 0 次或多次重複。（例如：\( a* \) 代表「」，「a」，「aa」，「aaa」...）
• \( + \)： 1 次或多次重複。（例如：\( a+ \) 代表「a」，「aa」，「aaa」...）
• \( ? \)： 0 次或 1 次重複——基本上就是讓該字元變成可選的 (optional)。
• \( | \) (選擇)： 意指「或」。(例如：\( a|b \) 代表「a」或「b」)
• \( ( ) \)： 用於將表達式的部分組合在一起。
範例：表達式 \( a(b|c)* \) 描述了以「a」開頭，後面接任意數量「b」或「c」的字串。這可以是「a」、「ab」、「ac」、「abbc」等等。
要避免的常見錯誤： 不要混淆 \( * \) 和 \( + \)。記住：星號 (Star) 可以是空值（\( * \) 包含空字串），但加號 (Plus) 至少必須有一個。
重點總結： RegEx 只是字串的「搜尋模式」。如果你能寫出一個模式，你就能定義一個語言！
4. 定義「正規語言」
這是「頓悟」的時刻，一切都串聯起來了。
如果一個語言滿足以下條件，我們就稱它為正規語言 (Regular Language)：
1. 它可以用一個正規表達式來表示。
或者
2. 它可以用一個有限狀態機 (FSM) 來識別。
等價規則
FSM 和正規表達式是等價的。 這意味著如果你能畫出一個 FSM 來識別某個模式，你就能為它寫出一個 RegEx，反之亦然。它們只是完成同一項工作的兩種不同方式！
類比：這就像食譜。一個人可能把它寫成一系列步驟（FSM），而另一個人可能將其寫成配料的數學公式（RegEx）。外觀不同，但做出來的蛋糕是一樣的！
快速複習：
• 如果 RegEx 可以描述它，它就是正規的。
• 如果 FSM 可以接受它，它就是正規的。
• RegEx \( \equiv \) FSM。
總結：融會貫通
我們今天涵蓋了很多內容！這就是「全貌」：
• FSMs 是處理輸入的機器。
• 集合為這些輸入的外觀提供了數學規則。
• 正規表達式是我們用來定義語言的簡寫模式。
• 如果一個 FSM 或 RegEx 適用於某種語言，那麼該語言在官方定義上就是正規的。
如果需要多讀幾遍也沒關係。計算理論就像一場拼圖遊戲——一旦 FSM 和 RegEx 的碎片拼湊在一起，你就會發現規律無處不在！你一定可以做到的！