适合读者：软考中级备考同学
阅读时间：3分钟
内容：正规式的定义、基本运算、正规集、常用等价关系、例题
1. 为什么需要正规式？
正规式（Regular Expression）是一种用特定符号表示字符串集合（即正规集）的代数表示法。它能够简洁地描述词法规则（如标识符、整数、运算符等），是词法分析的基础。软考中常考查正规式与正规集的转换，以及正规式的化简。
2. 基本定义
正规式：递归定义如下：
- ε\varepsilonε（空串）是正规式，表示集合{ε}\{\varepsilon\}{ε}。
- 若aaa是终结符，则aaa是正规式，表示集合{a}\{a\}{a}。
- 若rrr和sss是正规式，则以下也是正规式：
- r∣sr|sr∣s（或），表示集合L(r)∪L(s)L(r) \cup L(s)L(r)∪L(s)
- rsrsrs（连接），表示集合{xy∣x∈L(r),y∈L(s)}\{ xy \mid x \in L(r), y \in L(s) \}{xy∣x∈L(r),y∈L(s)}
- r∗r^*r∗（闭包），表示集合L(r)∗=⋃i≥0L(r)iL(r)^* = \bigcup_{i \ge 0} L(r)^iL(r)∗=⋃i≥0L(r)i（包含ε\varepsilonε）
- 有限次使用上述规则得到的表达式都是正规式。
正规集：正规式所表示的字符串集合。
3. 常用运算符号及优先级
| 运算符 | 含义 | 优先级（由高到低） |
|---|---|---|
| ∗^*∗ | 闭包（克林闭包） | 最高 |
| ⋅·⋅（连接） | 先后连接 | 中等 |
| ∣|∣（或） | 选择 | 最低 |
通常括号( )用于改变运算顺序。
4. 正规式表示的语言示例
| 正规式 | 正规集描述 |
|---|---|
| a∣ba|ba∣b | {a,b}\{a, b\}{a,b} |
| ababab | {ab}\{ab\}{ab} |
| a∗a^*a∗ | {ε,a,aa,aaa,… }\{\varepsilon, a, aa, aaa, \dots\}{ε,a,aa,aaa,…} |
| a∣b∗a|b^*a∣b∗ | {a,ε,b,bb,bbb,… }\{a, \varepsilon, b, bb, bbb, \dots\}{a,ε,b,bb,bbb,…}（注意优先级） |
| (a∣b)∗(a|b)^*(a∣b)∗ | 所有由aaa和bbb组成的字符串（包括空串） |
| a(a∣b)∗a(a|b)^*a(a∣b)∗ | 以aaa开头的、由aaa和bbb组成的字符串 |
| a∗ba^*ba∗b | 任意个aaa后跟一个bbb |
| (a∣b)∗aa(a∣b)∗(a|b)^*aa(a|b)^*(a∣b)∗aa(a∣b)∗ | 至少包含连续两个aaa的串 |
5. 常用正规式等价关系
| 等价关系 | 说明 |
|---|---|
| r∣s=s∣rr|s = s|rr∣s=s∣r | 交换律 |
| (r∣s)∣t=r∣(s∣t)(r|s)|t = r|(s|t)(r∣s)∣t=r∣(s∣t) | 结合律 |
| (rs)t=r(st)(rs)t = r(st)(rs)t=r(st) | 连接结合律 |
| r(s∣t)=rs∣rtr(s|t) = rs | rtr(s∣t)=rs∣rt | 分配律 |
| (s∣t)r=sr∣tr(s|t)r = sr | tr(s∣t)r=sr∣tr | 分配律 |
| εr=rε=r\varepsilon r = r\varepsilon = rεr=rε=r | 空串为单位元 |
| r∗=(r∗)∗=r∗r∗=ε∣r∗r^* = (r^*)^* = r^*r^* = \varepsilon | r^*r∗=(r∗)∗=r∗r∗=ε∣r∗ | 闭包性质 |
| (r∣s)∗=(r∗s∗)∗(r|s)^* = (r^*s^*)^*(r∣s)∗=(r∗s∗)∗ | 常见变形 |
6. 与有限自动机的关系
正规式、正规集、有限自动机（FA）三者等价：
- 每个正规式对应一个正规集，且能被一个有限自动机识别。
- 每个有限自动机所识别的语言都可以用一个正规式表示。
软考中常见题型：给定正规式，画出相应的状态转换图；或给定DFA，写出正规式。
7. 经典例题
题目1：设正规式r=(a∥b)∗abbr = (a\|b)^*abbr=(a∥b)∗abb，求它所表示的语言。
解析：(a∥b)∗(a\|b)^*(a∥b)∗表示任意个aaa或bbb组成的串（包括空串），后面紧跟abbabbabb。因此该正规式表示所有以abbabbabb结尾的、由aaa和bbb组成的字符串。
答案：{w∈{a,b}∗∣w 以 abb 结尾}\{ w \in \{a,b\}^* \mid w \text{ 以 } abb \text{ 结尾} \}{w∈{a,b}∗∣w以abb结尾}
题目2：写出表示“以aaa开头，后跟任意个bbb”的字符串的正规式。
解析：aaa开头：aaa；后面可以跟任意个bbb：b∗b^*b∗。连接起来：ab∗a b^*ab∗。
答案：ab∗a b^*ab∗
题目3：与正规式(ab)∗(ab)^*(ab)∗等价的是（ ）。
A.a∗b∗a^*b^*a∗b∗
B.a∗b∗a∗a^*b^*a^*a∗b∗a∗
C.(a∥b)∗(a\|b)^*(a∥b)∗
D.ε∥ab∥(ab)(ab)∥…\varepsilon\|ab\|(ab)(ab)\|\dotsε∥ab∥(ab)(ab)∥…
解析：(ab)∗(ab)^*(ab)∗表示空串或ababab重复多次的串（ab,abab,ababab,…ab, abab, ababab, \dotsab,abab,ababab,…）。选项Aa∗b∗a^*b^*a∗b∗可以生成aaa和bbb任意顺序但无ababab重复模式（如bababa也允许），不对。选项B同理。选项C包含所有a,ba,ba,b串，范围太大。选项D正是其定义。
答案：D
题目4：化简正规式(ε∥a)b∗(\varepsilon\|a)b^*(ε∥a)b∗。
解析：ε∥a\varepsilon\|aε∥a表示空串或aaa，即{ε,a}\{ \varepsilon, a \}{ε,a}。与b∗b^*b∗连接：{ε,a}⋅b∗=b∗∪ab∗\{\varepsilon, a\} \cdot b^* = b^* \cup a b^*{ε,a}⋅b∗=b∗∪ab∗。而b∗b^*b∗已包含在ab∗a b^*ab∗中？注意εb∗=b∗\varepsilon b^* = b^*εb∗=b∗，ab∗a b^*ab∗是单独的，所以整体就是b∗∥ab∗b^* \| a b^*b∗∥ab∗。由于b∗b^*b∗是ab∗a b^*ab∗的一部分？不，b∗b^*b∗生成所有仅含bbb的串，ab∗a b^*ab∗生成以aaa开头的串。二者无包含关系，所以化简后为b∗∥ab∗b^* \| a b^*b∗∥ab∗。进一步可写作(a∥ε)b∗(a\| \varepsilon) b^*(a∥ε)b∗，但通常保留原形即可。
答案：(ε∥a)b∗(\varepsilon\|a)b^*(ε∥a)b∗或b∗∥ab∗b^*\|ab^*b∗∥ab∗
8. 记忆口诀
正规式描述字符串，空串闭包连接或。
优先级：闭包高，连接次之或最低。
等价转换多练习，有限自动机可互换。
9. 给备考同学的一句话
正规式与正规集是词法分析的数学基础。软考中常考：
- 给定自然语言描述，写出正规式。
- 给定正规式，解释其表示的语言。
- 正规式的等价化简或与有限自动机的转换。
记住基本运算的含义：r∣sr|sr∣s（或）、rsrsrs（连接）、r∗r^*r∗（零次或多次重复）。多做题熟悉常见的等价关系，考试时就能快速写出正确答案。
🔔本专栏日更2篇，点击头像 → 专栏《软考中级高频考点》订阅
#软考中级 #软件设计师 #正规式 #正规集 #词法分析
