正規表示式（regular expression）

想像你要用一條簡短的公式描述一整個家族的字詞，而不是把它們一個一個列出來。正規表示式正是如此：它是一小段記號，透過說明如何構造字串來指名一個字串集合。有限自動機是一台讀入字串並回答是或否的機器，而正規表示式則是生成同一組字串的配方，兩者是同一件事的兩種視角。

正規表示式由幾個簡單的零件堆疊而成。基本情形是字母表 Σ（Sigma）中的單一符號、空字串 ε（epsilon），以及空集 ∅。在此之上用三種運算組合出更大的表示式：聯集（寫成 + 或 |，意思是「這個樣式或那個樣式」）、串接（把兩個樣式並排寫，意思是「先這個再那個」），以及 Kleene 星號（寫成單一個星號，意思是「零個或多個複本」）。例如在字母表 {a, b} 上，表示式 a(a+b)*b 描述了所有以 a 開頭、以 b 結尾的字串。

每個正規表示式都標示出一個語言，也就是一個字串集合，其定義是由內而外依照表示式的結構讀出。一個驚人的事實（Kleene 定理）是：你能這樣寫出的語言，恰好就是正規語言，與有限自動機所識別的類別完全相同。常見的混淆是：程式語言中的「正規表示式」加上了反向參照與前瞻等額外功能，已超出這個數學物件的範圍，因此工程工具與理論工具同名，卻不是同一件東西。