正规式与正规集

1. 考点：基础概念

正规式是描述程序语言单词的表达式。

1.1 正规式及其表示的正规集递归定义

对于字母表 Σ，其上的正规式及其表示的正规集可以递归定义如下：

1. ε 是一个正规式，它表示集合 L(ε) = {ε}。

2. 若 a 是 Σ 上的字符，则 a 是一个正规式，它所表示的正规集 L(a) = {a}。

3. 若正规式 r 和 s 分别表示正规集 L(r) = L(s)，则：

• r|s 是正规式，表示集合 L(r) ∪ L(s)；
• r·s 是正规式，表示集合 L(r)L(s)；
• r* 是正规式，表示集合 (L(r))*；
• (r) 是正规式，表示集合 L(r)。

1.2 重要说明

仅由有限次地使用上述三个步骤定义的表达式才是 Σ 上的正规式。

由此可见，正规式要么为空，要么由字母、或、连接、闭包运算符组成。

1.3 运算符优先级

• 闭包运算符 “*” 具有最高优先级
• 连接运算具有次高优先级
• 或运算符 “|” 具有最低优先级

2. 考点：常见正规式

字母表：Σ = {a, b}

正规式	正规集	举例
ab	字符串ab构成的集合	{ab}
a|b	字符串a、b构成的集合	{a, b}
a*	由0或多个a构成的字符串集合	{空, a, aa, aaa, a…a(n个a)}
(a|b)*	所有字符a和b构成的串的集合	{空, a, b, ab, aab, abb, baa, aba, …}
a(a|b)*	以a为首字符的a、b字符串的集合	{a, aa, ab, aab, aba, aaab, aaba, …}
(a|b)*abb	以abb结尾的a、b字符串的集合	{abb, aabb, babb, abaabb, abaaabb, …}

3. 经典例题

3.1 题目一

题目： 由字符a、b构成的字符串中，若每个a后至少跟一个b，则该字符串集合可用正规式表示为（ ）。

选项：

• A、​(b|ab)*
• B、​(ab*)*
• C、​(a*b*)*
• D、​(a|b)*

解析：

题目核心条件为“每个a后至少跟一个b”，意味着字符串中不能出现单独的a或连续的a（如"a"、"aa"等）。分析各选项：

• A、 ​ ​(b|ab)*​ ​：该表达式中，​b​后无限制，​a​后必定紧跟​b​（即​ab​作为一个整体）。生成的字符串如空串、b、ab、bb、bab、abab等，均满足“每个a后至少跟一个b”。 （正确）
• B、 ​ ​(ab*)*​ ​：​b*​表示0个或多个b，因此​a​后可能跟0个b（即​a​），产生如"a"、"aba"等不满足条件的字符串。 （错误）
• C、 ​ ​(a*b*)*​ ​：​a*​与​b*​均可为空，可能导致多个​a​连续出现或​a​后无​b​的情况，如"aa"、"a"等。 （错误）
• D、 ​ ​(a|b)*​ ​：表示任意由a、b构成的字符串，显然包含"a"、"aa"等不满足条件的串。 （错误）

正确答案：A。

‍