跳轉到

1959-正則表達式#

案件摘要#

1959 年，Stephen Kleene 的正則表達式理論完整版正式發表（1951 年 RAND 報告 → 1956 年論文 → 1959 年完整版）：以三個運算 \(rs, r|s, r^*\) 從原子構築出「正則語言」，並證明它們恰好等價於有限自動機。一門從神經網路數學誕生的記法，最終成為全世界程式設計師的日常工具。

前因 -- 為什麼會有這個案子#

  • 1943 年 McCulloch–Pitts 提出神經元的邏輯模型，用「事件串列」描述神經網路的行為。
  • 1951 年 Kleene 在 RAND 報告《Representation of Events in Nerve Nets and Finite Automata》中，試圖刻劃「神經網路能辨識哪些事件」。
  • Kleene 的偵探手法：發明一種代數記法（正則表達式）描述事件，再證明「正則表達式可描述的事件」=「有限自動機可辨識的事件」。這就是 Kleene 定理。
  • 歷史線索的三段式：1951 報告首次提出 → 1956 論文（《Representation of Events in Nerve Nets and Finite Automata》, Automata Studies）嚴格證明 → 1959 完整版修訂定型。

線索與推理 -- 數學式、程式、理論#

正則表達式的文法#

在字母表 \(\Sigma\) 上，正則表達式（regex）遞迴定義：

\[ r ::= \; a \;(\forall a \in \Sigma) \;\mid\; \epsilon \;\mid\; \emptyset \;\mid\; r s \;\mid\; r \mid s \;\mid\; r^* \]

各構件的語言語義：

表達式 語義（語言）
\(a\) \(\{a\}\) ，單一字元
\(\epsilon\) \(\{\epsilon\}\) ，空字串
\(\emptyset\) \(\varnothing\) ，空語言
\(rs\) （串接） \(\{xy : x \in L(r), y \in L(s)\}\)
\(r \mid s\) （聯集） \(L(r) \cup L(s)\)
\(r^*\) （Kleene star） \(\bigcup_{n \geq 0} L(r)^n = \{\epsilon, x_1x_2\ldots, \ldots\}\)

範例： \((a \mid b)^* a (a \mid b)^*\) 描述「含至少一個 \(a\) 的字串」； \(a(ab)^*\) 描述「 \(a\) 後接零或多個 \(ab\) 」。

Thompson 構造（regex → NFA）#

Ken Thompson（1968）將 Kleene 的構造系統化成可實作的歸納法：每個 regex 對應一個 NFA，由小到大組合：

  • \(a\) ：兩狀態、一條 \(a\) -邊。
  • \(rs\) ：串接——將 \(r\) 的接受狀態以 \(\epsilon\) -邊連到 \(s\) 的起始狀態。
  • \(r \mid s\) ：新起始狀態以 \(\epsilon\) -邊分連 \(r, s\) 的起始。
  • \(r^*\) ：新接受狀態， \(r\) 的接受狀態以 \(\epsilon\) -邊回連起始（形成循環），並有 \(\epsilon\) -邊跳過。
\[ \text{size}(NFA) = O(|r|) \]

NFA 狀態數與 regex 長度成線性關係，這是 Thompson 的關鍵貢獻（相較於直接 determinization 的指數爆炸）。

正則表達式 = 有限自動機的雙向構造（Kleene 定理）#

Kleene 定理：語言 \(L\) 是正則的 \(\iff\) \(L\) 被某個有限自動機接受。

\[ \exists\, r \;[L = L(r)] \iff \exists\, M \;[L = L(M)], \; M \text{ 為 DFA} \]

雙向構造： - regex → NFA：Thompson 構造（上述），再由子集構造（subset construction）去隨機化成 DFA。 - NFA/DFA → regex：狀態消去法（state elimination，Brzozowski/McNaughton–Yamada 形式）：對狀態 \(k\) 逐一消去，合併邊標籤：

\[ R_{ij}^{(k)} = R_{ij}^{(k-1)} \mid R_{ik}^{(k-1)} \left( R_{kk}^{(k-1)} \right)^* R_{kj}^{(k-1)} \]

最終從起始狀態到接受狀態的標籤即為 regex。代價：regex 可能指數膨脹（ \(O(2^{O(n)})\) ）。

Python re 模組與 Thompson NFA 模擬#

# --- Thompson NFA 構造與模擬（教學版） ---
class State:
    def __init__(self):
        self.eps = []        # epsilon 邊
        self.trans = {}      # 字元邊: char -> list[State]

def thompson(regex: str) -> State:
    """支援串接、|、* 的簡化遞迴下降構造（右結合解析）"""
    pos = [0]
    def parse_alt():
        n1 = parse_cat()
        if pos[0] < len(regex) and regex[pos[0]] == '|':
            pos[0] += 1
            n2 = parse_alt()
            s, e = State(), State()
            s.eps += [n1, n2]           # 聯集：分連
            e2 = State()                # 匯合（簡化：共用）
            return s
        return n1
    def parse_cat():
        states = [parse_star()]
        while pos[0] < len(regex) and regex[pos[0]] not in '|)':
            states.append(parse_star())
        for a, b in zip(states, states[1:]):
            a.eps.append(b)             # 串接：eps 邊連接
        return states[0]
    def parse_star():
        n = parse_atom()
        while pos[0] < len(regex) and regex[pos[0]] == '*':
            s, e = State(), State()
            s.eps += [n]
            # r* : 跳過 + 循環
            for st in _accepts_of(n): st.eps.append(s)
            n = s
        return n
    def parse_atom():
        c = regex[pos[0]]; pos[0] += 1
        s = State(); s.trans[c] = [State()]
        return s
    def _accepts_of(n): return [n]      # 簡化版：單一接受概念
    return parse_alt()

def match(nfa: State, text: str) -> bool:
    """NFA 模擬：epsilon-closure + 字元轉移，O(len(text) * |NFA|)"""
    current = {nfa}
    def closure(states):
        stack, seen = list(states), set(states)
        while stack:
            s = stack.pop()
            for t in s.eps:
                if t not in seen:
                    seen.add(t); stack.append(t)
        return seen
    current = closure(current)
    for ch in text:
        nxt = set()
        for s in current:
            if ch in s.trans:
                nxt |= set(s.trans[ch])
        current = closure(nxt)
        if not current:
            return False
    # 簡化：檢查是否有狀態帶有「接受」標記（此教學版以最後狀態無出邊近似）
    return any(not s.eps and not s.trans for s in current)

# --- 實務對照：Python re 模組 ---
import re
assert re.fullmatch(r"(a|b)*a(a|b)*", "bba")   # 含至少一個 a
assert re.match(r"^\d{4}-\d{2}-\d{2}$", "2026-09-30")   # 日期格式
assert re.findall(r"\b\w+\b", "hello regex world") == ["hello", "regex", "world"]
print("re 模組與 Thompson NFA：範例通過")

grep/regex 在實務程式設計的影響#

  • 1968 年 Ken Thompson 在 UNIX 上實作 ed/grep，首次將 regex 帶入作業系統工具。
  • grep（Global Regular Expression Print）成為 UNIX 哲學的核心工具；regex 擴散到 awk、sed、Perl（Larry Wall 1987 大幅擴充）、PCRE、Python re、JavaScript RegExp、Java/C# 等。
  • 應用場景：詞法分析器（lex/flex）、日誌解析、輸入驗證、搜尋替換、基因序列比對（正則近似）、網頁爬蟲。
  • 效能戰場：Rust 的 regex crate 與 RE2（Google, 2010）堅持線性時間 Thompson NFA 模擬，拒絕回溯（backtracking）以避免「災難性回溯」（catastrophic backtracking, \(O(2^n)\) ）——正是 Kleene/Thompson 路線的現代復興。

結案 -- 後果與影響#

  • 結案：Kleene 定理確立「正則表達式 = 有限自動機」，記法與機器合而為一。
  • 理論影響：正則語言成為 Chomsky 階層 Type-3 層；泵引理、Myhill–Nerode 定理完善其理論；Brzozowski 導數（1964）提供另一條代數路線。
  • 實務影響：regex 成為程式設計師的「第二母語」；從 UNIX 工具到現代語言標準庫無所不在。
  • 深遠影響：regex 是「高階記法自動編譯成低階機器」的最早成功範例之一，預示了編譯器、DSL、甚至 LLM 時代的提示詞工程的「描述即程式」哲學。災難性回溯問題則提醒：理論上的線性時間演算法（Thompson）與實務實作的選擇同樣重要。

關鍵人物與文獻#

  • Stephen Kleene（1909–1994）：《Representation of Events in Nerve Nets and Finite Automata》, RAND Report RM-704, 1951；《Automata Studies》, 1956；完整版 1959。
  • Warren McCulloch / Walter Pitts：1943 神經元模型，regex 的生物學源頭。
  • Michael Rabin / Dana Scott：1956 年 NFA/DFA 等價性與有限自動機理論（Turing 獎 1976）。
  • Ken Thompson：1968 年 UNIX grep/QED 的 regex 實作；2007 年《Regular Expression Matching Can Be Simple and Fast》重申 Thompson NFA 路線。
  • Janusz Brzozowski：1964 年正則表達式導數，regex→DFA 的代數方法。