正規表示式的代數恆等式

正如普通代數有像 x + 0 = x 與 x × 1 = x 這樣的規則讓你化簡、重排公式，正規表示式也有自己的定律。這些恆等式說明兩個不同的表示式何時標示同一個語言，於是你可以把一個換成更簡單的等價物，而不改變它所匹配的內容。它們在那三個運算之上構成一個小代數（有時稱為 Kleene 代數）。

關鍵的恆等式牽涉聯集、串接與那兩個特殊原子。聯集滿足交換律（R+S = S+R）、結合律與冪等律（R+R = R），並以 ∅ 為單位元素（R+∅ = R）。串接滿足結合律，並以 ε 為單位元素（Rε = εR = R），但不滿足交換律；空集則吸收它（R∅ = ∅R = ∅）。星號遵守 ∅* = ε（無物的零個或多個複本就只是空字串）、ε* = ε，以及雙星定律 (R*)* = R*。串接對聯集也滿足分配律：R(S+T) = RS + RT 且 (S+T)R = SR + TR。這裡的「=」意指「標示相同的語言」，而非「是相同的符號串」。

這些定律在理論與實務上都重要。在理論上，它們讓你能以純粹的改寫證明兩台機器或兩個表示式等價，並支撐 Kleene 定理的代數證明。在實務上，regex 最佳化器與詞法分析器產生器用它們在建構自動機之前縮小表示式。一個提醒：雖然這些恆等式是可靠的，但要完整地公理化全部為真的 regex 等價關係，其複雜程度出人意料，所以別假設每條看似合理的「定律」都成立；請對照所標示語言的歸納定義加以驗證。