17.2.4 正规式与正规集

正规式描述的是一组字符串的模式，正规集是这组字符串本身。可以把正规式理解为“规则”，把正规集理解为“规则能生成或匹配的所有串”。

基本运算

设字母表为 {A, B}。

正规式	含义	示例
A	只包含字符串 A 的集合	{A}
`A	B`	或，A 或 B
AB	连接，先 A 后 B	{AB}
A*	零个或多个 A	ε, A, AA, AAA, ...
A+	一个或多个 A	A, AA, AAA, ...
`(A	B)*`	由 A、B 任意组成的串

这里的星号 * 很容易出错：它允许重复零次，所以一定包含空串 $\epsilon$。

用位置表达约束

正规式不是只靠“有没有某个字符”，更常通过字符所在位置表达约束。

约束	正规式	含义
以 A 开头	`A(A	B)*`
以 ABB 结尾	`(A	B)*ABB`
只由若干个 AB 块组成	(AB)*	ε, AB, ABAB, ...
每个 A 后至少跟一个 B	`(B	AB)*`

正规式与有限自动机的关系

正规式、正规文法和有限自动机描述的是同一类语言：正规语言。一个模式可以写成正规式，也可以画成自动机。考试经常让你在二者之间互相判断。

flowchart LR
  A["正规式"] <--> B["正规集"]
  A <--> C["有限自动机"]
  C --> D["词法分析器"]

解题：用反例排除

正规式选择题最稳的方法不是死展开，而是找反例。

1. 先列出必须满足的约束，如“必须以 0 结尾”“不能出现 01”“每个 A 后要有 B”。
2. 对每个选项试一个最短反例。
3. 如果选项能表示题目不允许的串，排除。
4. 如果题目允许的串选项表示不了，也排除。

例如自动机能识别 0 和 10 任意拼接的串，则候选应类似 (0|10)*。如果某选项能生成 01，而自动机不接受 01，就不是等价表达式。

小练习

题：(0|10)* 能否生成字符串 010？

答：能。可以分解为 0 和 10 两个块。

自查

1. 正规式和正规集的区别是什么？
2. 为什么 (A|B)* 包含空串？
3. 判断两个正规式是否等价时，为什么找反例很有效？