正则表达式
一种用于表示字符串集合的小型代数。
语法与含义在字母表
Σ上，一个正则表达式由原子∅（空集）、ε（空串）以及每个符号a∈Σ构成，并通过三种运算组合起来：
- 并（union）
R | S— 属于R或S的字符串；- 连接（concatenation）
R S— 一个R-字符串后面接一个S-字符串；- 克莱尼星号（Kleene star）
R*— 零个或多个R-字符串依次相连。 优先级：*> 连接 >|。
例子：a* b* 表示若干个 a 之后接若干个 b；(0|1)* 01 表示以 01 结尾的二进制串；(aa)* 表示长度为偶数的 a 串。
把一个正则表达式画成一台机器，往往比一串符号更清楚——每条边就是要读入的字符，从起始状态到接受状态的一条路径，拼出的正是该正则表达式所匹配的一个词：
它是一种代数（克莱尼代数）
并运算满足结合律、交换律、幂等律，单位元是 ∅；连接运算满足结合律，单位元是 ε，零元是 ∅；星号运算满足 R* = ε | R R* 以及 (R*)* = R*。这些正是克莱尼代数（Kleene algebra）的公理——其中 R* = ε | R R* 这条定律是一个不动点方程：R* 是方程 X = ε | R X 的最小解。
与野生环境中的"正则表达式"并不相同
编程语言里的正则表达式库（如 PCRE）加入了反向引用（backreferences）（\1）——它能匹配 ww 这样的串，但这样一来就不再是正则的了（需要用到记忆）。这里所说的"正则表达式"指的是纯粹的克莱尼代数片段；正是这个片段，通过 regular-equivalences 与 finite-automata 等价。