形式陈述

字母表 $\Sigma$$\mathrm{\Sigma }$ 上的正则表达式递归定义：$\varnothing$$\varnothing$、$\varepsilon$$\epsilon$ 及每个 $a\in\Sigma$$a\in \mathrm{\Sigma }$ 是正则表达式；若 $R,S$$R,S$ 是正则表达式，则 $(R\mid S)$$(R\mid S)$、$RS$$RS$ 与 $R^*$$R^{\ast }$ 也是。其语言语义为

$$ L(R\mid S)=L(R)\cup L(S),\quad L(RS)=L(R)L(S),\quad L(R^*)=L(R)^*. $$$$L(R\mid S)=L(R)\cup L(S),L(RS)=L(R)L(S),L(R^{\ast })=L(R{)}^{\ast }.$$

直觉

正则表达式用三种有限组合描述字符串模式：选择、顺序拼接和有限次重复。表达式是语法树，真正被描述的是它的语言。

例子与边界

表达式 $(0\mid1)^*01$$(0\mid 1{)}^{\ast }01$ 描述所有以 $01$$01$ 结尾的二进制串。理论正则表达式不含反向引用、递归子模式等扩展；许多工程“regex”加入这些功能后可描述非正则语言，不能直接套用有限自动机结论。

推论与应用

Kleene 定理证明正则表达式与有限自动机表达能力完全相同。正则表达式广泛用于词法分析、文本搜索和输入格式校验。

参考资料

• John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Pearson, 2006，§3.1。
• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013，§1.3。