計算理論：正規表達式與正規語言
你好！歡迎來到計算理論中最實用且迷人的領域之一：正規表達式 (Regular Expressions)。
別被這個名字嚇到了。簡單來說，正規表達式（通常簡稱為 "Regex" 或 "RE"）只不過是用來描述和匹配字串模式的超強工具。
如果你曾經在文書處理軟體中使用過「尋找與取代」功能，或者在註冊網站時檢查過電子郵件地址的格式是否正確，其實你已經接觸過正規表達式了！
在本章中，我們將學習如何編寫這些模式，並理解它們與最簡單的抽象計算機器——有限狀態機 (Finite State Machine, FSM) 之間深厚的聯繫。
1. 理解正規語言
計算科學中的「語言」是什麼？
在計算理論的脈絡下，語言 (language) 單純是指由特定字母表 (alphabet) 所構成的一組有效字串（字元序列）。
- 範例： 如果字母表是 \(\{0, 1\}\)，那麼一種語言可以是所有以 0 開頭的字串集合（例如：0, 01, 000, 0101...）。
正規語言 (Regular Language) 是指能夠使用正規表達式精確描述，或是能被有限狀態機 (FSM) 所識別的語言。這是我們在此領域中所研究最基礎的語言類型。
什麼是正規表達式 (RE)？
正規表達式是用於定義搜尋模式的正式字元序列。你可以把它想像成有效字串的「藍圖」。
類比： 想像你正在資料庫中尋找每一張汽車車牌。你不知道確切的車牌號碼，但你知道它的模式：三個字母，接著兩個數字，最後是一個字母。正規表達式就是你定義該模式的方法。
重點總結： 如果一個模式可以由正規表達式描述，那麼它就屬於正規語言。
2. 基本元字元（建構組塊）
要編寫 RE，我們使用標準字元（如 'a', '1', '@'）結合稱為元字元 (metacharacters) 的特殊符號。這些元字元定義了重複和選擇的規則。
我們將使用字母表 \(\{a, b, c\}\) 作為以下範例。
2.1 重複與選擇性
這些元字元控制前面的字元或群組允許出現的次數。
1. Kleene 星號： *（零次或多次重複）
* 元字元表示前面的元素可以出現零次或多次。它可能是最基礎的重複運算子。
-
RE:
a*
匹配： "", "a", "aa", "aaa", "aaaaa"... -
RE:
b(a)*
匹配： "b"（當a重複 0 次時）, "ba", "baa", "baaa"...
記憶小撇步： * 看起來像雪花，它可以覆蓋零空間（空字串）或大量的空間（無限重複）。
2. 加號： +（一次或多次重複）
+ 元字元表示前面的元素必須出現一次或多次。它類似於 *，但它不能匹配空字串。
-
RE:
a+
匹配： "a", "aa", "aaa"...（但不能匹配空字串 ""） -
RE:
a(bc)+
匹配： "abc", "abcbc", "abcbcbc"...
3. 問號： ?（選用/零次或一次重複）
? 元字元表示前面的元素是可選的，它出現零次或一次。
-
RE:
colou?r
匹配： "color" 或 "colour"（對於處理不同的拼寫方式很有用！） -
RE:
a(b)?c
匹配： "ac" 或 "abc"
2.2 交替與分組
4. 交替/OR 運算子： |
| 元字元用於指定交替，意即「這個或那個」。它在兩個或多個表達式之間提供選擇。
-
RE:
cat|dog
匹配： 正確的 "cat" 或正確的 "dog"。 -
RE:
a(b|c)d
匹配： "abd" 或 "acd"。
5. 分組： ()
括號 () 用於將正規表達式分組，以便將重複或交替運算子應用於整個組別。
-
如果你寫
ab+，+只作用於 'b' (a, abb, abbb...)。 -
如果你寫
(ab)+，+則作用於整個組別 'ab' (ab, abab, ababab...)。
範例：匹配帶有特定副檔名的簡單檔案名稱。
RE: (data|file).txt
匹配： "data.txt" 或 "file.txt"
✎ 快速複習：元字元含義
*: 零次或多次+: 一次或多次?: 零次或一次（可選）|: OR（交替）(): 分組
3. 字元類別
字元類別允許你為字串中的單一位置指定一組可接受的字元。這些類別使用方括號 [] 定義。
1. 指定字元集
將字元放入方括號內代表「匹配此集合中的任何單一字元」。
-
RE:
[aeiou]
匹配： 任何單一母音（例如：'a', 'e', 'i', 'o' 或 'u'）。 -
RE:
[CH]at
匹配： "Chat" 或 "Hat"。（課程大綱指定此格式。）
2. 字元範圍
若要指定大範圍的字元（如所有數字或所有大寫字母）而無需一一列出，可以使用連字號 -。
-
RE:
[0-9]
匹配： 0 到 9 之間的任何單一數字。 -
RE:
[A-Z]
匹配： A 到 Z 之間的任何單一大寫字母。 -
RE:
[a-zA-Z0-9]+
匹配： 字母（大寫或小寫）與數字的任何組合，且長度至少為一個字元。
你知道嗎？ 正規表達式對於語法分析 (lexical analysis)（編譯器的第一階段）至關重要，它們被用來識別關鍵字、識別碼和數字等 Token。
RE 建構範例
讓我們為一種簡單的變數命名規則建構一個 RE：必須以字母開頭，之後可以包含字母或數字。
- 必須以字母開頭：
[a-zA-Z] - 隨後是零次或多次的字母或數字：
[a-zA-Z0-9]*
組合後的 RE： [a-zA-Z][a-zA-Z0-9]*
- 匹配： "X", "Var1", "myVariable", "count3"
- 不匹配： "1X", "345"
要避免的常見錯誤： 混淆 a|b* 與 (a|b)*。
前者匹配 'a' 或零/多次的 'b'（例如：'a', 'b', 'bb', 'bbb'）。
後者匹配任何 'a' 和 'b' 的序列，包括空字串（例如：'ab', 'aba', 'baab'）。分組是非常重要的！
4. 理論連結：FSM 與正規語言
本節將形式理論帶回我們的討論。在計算理論中，有限狀態機 (FSM) 是最簡單的計算模型。
4.1 等價原則
這裡最重要的概念是 RE 與 FSM 之間的關係：
正規表達式與 FSM 是定義正規語言的等價方法。
這意味著對於你編寫的每一個正規表達式，都可以設計一個對應的 FSM（狀態轉換圖），它所接受的字串集合完全相同。反之，對於任何 FSM，你也可以寫出描述該語言的正規表達式。
- 如果一個語言可以用正規表達式表示，它就是一個正規語言。
- 如果一個語言可以被 FSM 識別，它就是一個正規語言。
4.2 從 FSM 寫出 RE
你必須有能力寫出與給定 FSM 識別相同語言的正規表達式，反之亦然：設計一個 FSM 來識別與給定正規表達式相同的語言。
範例：從簡單的 FSM 寫出 RE。
想像一個 FSM，它接受以下形式的字串：一個 'a'，接著任意數量的 'b'，最後是一個 'c'。
- FSM 從狀態 S0 開始。
- 在輸入 'a' 時，從 S0 出發的唯一轉換會進入狀態 S1。
- S1 在輸入 'b' 時會循環回到自身。
- 在 S1 輸入 'c' 時，會進入最終（接受）狀態 S2。
逐步建構：
- 字串必須以 'a' 開頭： (
a) - 'b' 可以重複零次或多次（S1 的循環）： (
b*) - 字串必須以 'c' 結尾： (
c)
最終的正規表達式為： ab*c
範例 2：使用交替
想像一個 FSM，它接受以 '0' 或 '1' 開頭，後接任意數量 '0' 的字串。
RE: (0|1)0*
這能匹配 "0", "1", "000", "10", "1000" 等。
為什麼這很重要？
FSM 與 RE 之間的等價性是許多實用計算應用的基礎，特別是在解析、搜尋和驗證資料結構方面。如果你能用 RE 定義模式，你就知道一個簡單且高效的 FSM 可以處理該計算。
💯 考試重點摘要
你必須熟練於：
- 理解並應用五個關鍵元字元：
*,+,?,|, 以及()。 - 使用字元類別（例如
[A-Z]或[0-9]）來表示字元集合。 - 陳述形式關係：正規表達式與 FSM 描述的是同一組語言（正規語言）。
- 在 FSM 圖表/描述與其對應的正規表達式之間進行模式轉換。