正規表示式所標示的語言

正規表示式只是紙上的一串符號，就像寫下來的食譜。它所標示的語言則是那份食譜真正產出的字串集合，就像你照著做所得到的菜餚。我們用 L(R) 表示「R 所標示的語言」。把公式與其意義分開來看，是清晰思考正規表示式的關鍵。

L(R) 是歸納定義的，沿著 R 的結構由原子向外展開。基本情形設定 L(a) = { a }（對符號 a）、L(ε) = { ε }、L(∅) = { }。歸納情形則說：L(R+S) = L(R) ∪ L(S)（兩語言的聯集）、L(RS) = L(R) 與 L(S) 的串接（R 的每個字串後接 S 的每個字串）、L(R*) = L(R) 的 Kleene 星號（零個或多個串接的複本）。要找出任何表示式的意義，你就由內而外套用這些規則。例如 L((a+b)c) 先建出 L(a+b) = { a, b }，再把每一個與 c 串接，得到 { ac, bc }。

正是這個歸納定義讓正規表示式成為精確的數學，而非含糊的樣式談論。它也說明了一個微妙之處：兩個看起來不同的表示式可以標示同一個語言。例如 a* 與 (a*)* 都標示 { ε, a, aa, ... }，儘管符號串不同。當兩個表示式標示相同的語言時，我們稱它們等價，而證明這類等價正是代數恆等式的用途所在。