從一個模式到它所命名的集合
在本階梯的第 1 篇裡，你學會了用三種運算來書寫模式——聯集、串接，以及 Kleene 星號。現在我們要邁出賦予這些塗鴉意義的一步。正規表示式是一串有限的符號、一個語法物件——但每一個格式正確的正規表示式都表示一個語言，也就是一個確定的字串集合。你要養成的關鍵習慣，是在腦中把這兩件事分開：表示式是食譜，語言是菜餚。兩份不同的食譜可以煮出完全相同的一道菜，而本篇大半都在談這究竟何時發生。
這個定義是用遞迴建立的，起點是字母表 Σ（Sigma，即允許符號的有限集合）上的三個微小基本情形。第一，空集合符號 ∅ 表示空語言 { }——完全沒有任何字串。第二，空字串的符號（寫作 epsilon）表示只含一個元素的語言 { epsilon }，其中只有那個長度為零的字串。第三，Σ 中每個單一符號 a 表示只含一個元素的語言 { a }。整個地基就是這樣：一個正規表示式的最底層，不外乎是「什麼都沒有」、「只有空字串」，或「只有一個字母」。所有更豐富的東西，都由這些經三種運算拼裝而成。
三種運算作為集合的食譜
現在沿著遞迴往上爬。若 R 與 S 是正規表示式，分別表示語言 L(R) 與 L(S)，則複合表示式所表示的語言，由你已認識的集合運算構成。聯集 R+S（有些書寫成 R|S）表示 L(R) ∪ L(S)：兩邊任一者中的所有字串。串接 RS 表示「把一個取自 L(R) 的字串接在一個取自 L(S) 的字串前面」所得的所有字串，正式寫作 { xy : x 屬於 L(R)、y 屬於 L(S) }。而星號 R* 表示「把取自 L(R) 的零個或多個字串黏接起來」，關鍵是它永遠包含 epsilon（即零個複本的情形）。紙面上的每個運算子，都是一道建構集合的精確指令。
這個比喻藏了兩個警告。第一，語言的串接，並不等於挑一個字串重複它：在 (a+b)(a+b) 中，兩個因子是各自獨立選取的，所以它表示 { aa, ab, ba, bb }，而非只有 { aa, bb }。第二，星號不是「同一個字串重複很多次」——a* 表示 { epsilon, a, aa, aaa, … }，但 (ab)* 表示 { epsilon, ab, abab, … }，黏接的是整個字串、而非單一字母。這裡也是該丟棄一個誘人謬誤的第一處：「正規」不等於「有限」。 a* 表示一個無限語言，但它正規得不能再正規。有限性與正規性根本是兩個不同的問題。
expression denotes (the language)
---------- ----------------------
(empty set) /\ { } -- no strings
epsilon { epsilon } -- just the empty string
a { a } -- one one-letter string
R + S L(R) union L(S)
R S { xy : x in L(R), y in L(S) }
R* { epsilon } union L(R) union L(R)L(R) union ...
example: (a+b)*ab = every string over {a,b} that ENDS in ab
a*b* = some a's (maybe none) then some b's (maybe none)
NOTE: a*b* is NOT { a^n b^n }優先順序、括號與代數恆等式
因為我們把表示式寫在同一行上，就需要規則來決定誰先結合，正如 2 + 3 × 4 意指 2 + (3 × 4)。標準的優先順序是：星號最緊，其次串接，聯集最鬆。所以 ab*+c 會被剖析為 (a(b*)) + c，而不是 a((b*+c)) 或別的什麼。當你想要不同的分組時，就動用括號：(ab)* 對整塊 ab 取星號，而 ab* 只對 b 取星號。正確讀出優先順序，是「我的正規表示式明明對、做的事卻錯」最常見的單一肇因，所以動用它之前，先放慢、先剖析。
現在來談兩份食譜何時煮出同一道菜。有少數幾條代數恆等式永遠成立，因為它們是關於所表示集合的真實事實。聯集滿足交換律與結合律（R+S = S+R），但串接不滿足交換律：ab 與 ba 表示不同的語言。有些恆等式牽涉基本情形：∅ 是聯集的單位元（R+∅ = R），卻是串接的零元（R∅ = ∅）；而 epsilon 是串接的單位元（R·epsilon = R）。星號相關的最漂亮：∅* = epsilon（「沒有東西」取零個或多個複本，就只是空字串）、epsilon* = epsilon，以及 (R*)* = R*。
通往自動機的橋樑：Kleene 定理
這裡就是讓我們有資格把這些語言叫作「正規」的回報。Kleene 定理說，三種不同的描述挑出的，恰好是同一族語言：一個語言能被某個正規表示式表示，若且唯若它能被某台有限自動機辨識——而我們已知 DFA 與 NFA 辨識的是同一個類別，即正規語言。所以「你能用三種運算寫出的模式」與「一台有限記憶的機器能判定的語言」，是同一枚硬幣的兩面。接下來兩篇會詳細證明兩個方向；這裡我們只勾勒橋為何站得住，好讓這個等價不像是巧合。
正方向（正規表示式 → 自動機）依循你剛學到的遞迴。既然每個正規表示式都由基本情形經三種運算建成，那麼只要為每個基本情形建一台小機器，再說明如何就聯集、串接與星號組合這些機器即可。這種遞迴式的隨插即用，正是 Thompson 構造法，下一篇會逐步走過；它產生一台帶有無害 epsilon 跳躍的 NFA，這些跳躍逐括號地映照表示式的結構。反方向（自動機 → 正規表示式）則一次拔掉機器中的一個狀態，把存留下來的箭頭重新標記為正規表示式，直到只剩一條從起始到接受的箭頭——那條存留的標籤就是答案。
- 基底機器：為每個基本情形建一台只有一條箭頭的 NFA——∅（沒有任何接受路徑）、epsilon（一條通往接受狀態的 epsilon 箭頭）、a（一條通往接受狀態的 a 箭頭）。
- 聯集 R+S：加一個新起始狀態，用 epsilon 同時跳進 R 的機器與 S 的機器，使任一者皆可成功——這正是非確定性「分裂出分身」的手法。
- 串接 RS：用 epsilon 把 R 的接受狀態連到 S 的起始狀態，使 R 一完成就把接力棒直接交給 S。
- 星號 R*：加一個全新的起始兼接受狀態（使 epsilon 被接受），並加一條 epsilon 箭頭把 R 的接受狀態繞回 R 的起始狀態，允許零次、一次或多次重複。
從理論到真實世界的正規表示式——以及理論止步之處
Kleene 定理不只優雅；它正是你的文字編輯器搜尋框、以及編譯器第一階段得以運作的原因。一個語彙分析器（把原始碼切成數字、名稱、運算子等詞元的掃描器）的做法，是替每一種詞元寫一個正規表示式、把每個編譯成一台有限自動機，再合併成一台機器，在單一次由左到右的掃描中分類輸入。因為這引擎本質上是一台 DFA，它的執行時間與輸入長度成正比——線性、可預測、沒有意外。這就是理論在你每次編譯程式、或 grep 一份記錄檔時所繳的房租。
但對「數學物件」與「沿用其名的工程工具」之間的落差，要誠實以對。許多程式語言的正規表示式引擎加入了超出三種運算的功能——最顯著的是反向參照，它讓模式中較後的部分要求一份與較早群組所匹配內容相同的複本。反向參照可以描述可被證明非正規的語言（例如「某個字串，接著同一個字串再來一次」），所以一個用了它的「regex」其實已經不再表示一個正規語言了——它悄悄踏出了理論之外。先行斷言（lookahead）與環視（lookaround）也類似：很方便，但不屬於那個乾淨的 Kleene 世界。
而且代價是真實的。一旦引擎用回溯來支援這些額外功能，某些看似無辜的模式可能耗費與輸入長度成指數的時間——這就是令人聞之色變的災難性回溯：像 (a+)+ 這樣的模式在一個全是 a 的長字串上啃咬時，會去探索天文數字般多種拆分方式。一個純數學的正規表示式，編譯成 DFA 後，永遠不會有這個問題；它總是線性的。教訓是：數學保證你得到快速、行為良好的模式，而那些額外的工程功能，正是這份保證可能失守之處。