CSCI3130 L03 Part 1 正则表达式

课程：CSCI3130 Formal Languages and Automata Theory · 资料包，学期待核 本讲：L03 Part 1 正则表达式 · 原件 L03-正则表达式-资料包.pdf（本地课件） p.1–25 定位：把字符串集合压缩成有明确语义的表达式。 前后：下一份 L03-P2-表达式与自动机.md

本讲导航

1. P1 正则表达式：p.1–25。
2. P2 表达式与自动机：p.26–54。
3. P3 正则文法：p.55–101。
4. P4 结尾小测：p.102–104，Outline 之外实际存在的尾段。

p.1 标题页；p.2 Outline，先学表达式，再证明与有限自动机等价，最后连接文法。

用运算描述一个语言（p.3–5）【新】

p.5 A regular expression is not a language

p.3 把列举、条件描述与运算描述并列。列出几个元素不能表达无限集合的全部成员；条件描述虽准确，却未必直接变成机器。p.4 引入正则表达式：以字母为原料，用并、连接、闭包和括号组合。p.5 区分语法对象与其含义：纸面上的表达式是一段有限文字，它表示的语言却可以无限。就像算式与算式的值不同，不能把表达式的字符数误当成语言大小。

把 p.3 的三种描述实际写全：有限集合可列成 $\{a,aa,aba,aca\}$；按条件可说“某字母出现次数满足指定约束”；按语言运算可写 $\{aa,ab\}^{\ast}\cup\{b\}\{bb\}^{\ast}$。最后一个集合的成员或者是任意多个 aa/ab 块的连接，或者是奇数个 b。对应的 RE 是 $(aa+ab)^{\ast}+b(bb)^{\ast}$。前者是一个集合，后者是表示这个集合的有限表达式，所以规范写法是 $L(r)=\cdots$，不能把集合 L 和表达式 r 的类型混淆。

基本构件和合法写法（p.6–8）

p.7 A string is a regular expression iff it can be derived from the primitive regular expressions by a finite number of applications of the rules in (2).

p.6 的 $(a+bc)^{\ast}$ 允许每轮选一个 a 或一整个 bc，再连接有限轮，也允许零轮得到空串。这里加号是二选一，不是字符串里的加号。p.7 的基本构件为 $\varnothing$、$\lambda$ 和单个字母；若已有合法表达式，就能取并、连接、星号及括号。这个递归定义同时规定了什么不能直接写。

p.8 的 $(a+b\cdot c)^{\ast}\cdot(c+\varnothing)$ 合法；$(a+b+)$ 缺少最后一个操作数。$a^n$ 若 n 未被固定，不是基本语法定义给出的一个表达式。$a^+$ 可作为 $aa^{\ast}$ 的缩写，但不能拿缩写替代定义。$\varnothing$ 表示没有任何字符串，$\lambda$ 表示空串，二者不互换。

表达式如何解释成集合（p.9–11）

p.9 L(r ) : language of regular expression r

p.9 的 $L(r)$ 是解释函数：输入一个表达式，输出一整个语言。p.10 给出起点：$L(\varnothing)=\varnothing$，$L(\lambda)=\{\lambda\}$，$L(a)=\{a\}$。p.11 逐层解释复合表达式：加号变集合并，连接变语言连接，星号变零次或多次连接。这不是形式替换游戏；它保证每个合法表达式都能从有限语法树的叶子往上解释。

补充算例（为演示自取）：$L(a+\lambda)=\{a,\lambda\}$，所以 $L((a+\lambda)b)=\{ab,b\}$。空串的长度零，但在集合里仍算一个元素；它与 b 连接不会增加字母。

优先级先决定切分（p.12–14）

p.12 的 $(a+b)a^{\ast}$ 先选 a 或 b，再接任意多个 a，因此得到正长度的纯 a 串以及 b 后接若干 a。p.13 的运算优先级为星号、连接、并；$ab+c$ 表示 ab 或 c，不能读成 $a(b+c)$。

p.14 的 $(a+b)^{\ast}(a+bb)$ 中，前半段允许任意二进制字母串，后半段强制最后一个 a 或最后两个 bb。空串、单个 b 不被接受；a 与 bb 分别由空前缀取得。判断表达式时先找最外层连接，再解释各块，避免把局部星号错误扩大到全式。

计数与局部禁用条件（p.15–17）

p.15 的 $(aa)^{\ast}(bb)^{\ast}b$ 要求所有 a 在所有 b 前，并且 a 偶数个、b 奇数个。星号每次加两个，尾端额外的 b 负责奇偶偏移；它不描述任意次序但计数满足条件的串。

题面（本讲 p.16）

p.16 For $\Sigma=\{0,1\}$, give a regular expression r such that

$L(r)=\{w\in\Sigma^{\ast}:w\text{ has at least one pair of consecutive }0\}$.

公式按讲义重排。

用 $(0+1)^{\ast}00(0+1)^{\ast}$：中间固定一处00，左右任意。多次出现00也允许，因为题目只要求至少一次。

p.17 反过来不允许00，可写 $(1+01)^{\ast}(0+\lambda)$。前面每个0都和其后一个1绑在01块里，唯一可能没后继的0放在最后。反方向，任意不含00的串都可按这个规则分块，因此既不漏也不多。单独检验空串、0、1、01；四个都能生成。00无分块方式。

把不含 00 的反向证明真正拆一次（补充自取串）：对 1010110，从左读起，遇 1 单独拿走；遇 0 则检查下一位。只要它不是末尾，因禁用 00，下一位必为 1，拿走整个 01。于是分块为 1 / 01 / 01 / 1 / 0，前四块属于 $1+01$，最后孤立的 0 属于 $0+\lambda$。每一步至少拿走一个字符，所以过程终止。若最后不是 0，末块选择空串即可。这给出任意合法串的分块算法，补上“都能生成”的证明；若某一步 0 后又是 0，恰好暴露非法串，不能硬分块。

等价与有限语言（p.18–20）

p.18 Regular expressions r1 and r2 are equivalent if L( r1 ) = L( r2 )

p.18 的等价比较的是集合而非长相。p.19 两个“不含00”的表达式若不同，只要双向解释出的串相同便等价。p.20 的有限语言 $\{a,aa,aba,aca\}$ 可以直接用 $a+aa+aba+aca$ 表示：并列每个完整成员，不对单个字母随意加星号，否则会凭空增加无限多串。

p.17、19 的另一种原式也需要能独立读懂：

每个循环块由若干 1、一个 0、至少一个 1 组成，因此其中的 0 不会挨在一起；最后允许另加一个 0。为什么还加第二项？当没有任何内部的 0 时，需要自由生成纯 1 串及其后接一个 0；前面星号取零轮只剩 $0+\lambda$，不能独自产生 111。故补上第二项后才与 $(1+01)^{\ast}(0+\lambda)$ 同语言。p.21 的另一写法 $(00+01+10+11)^{\ast}$ 把两位的四种可能全部列出，与后文的两位分块式相同。

长度、后缀和奇偶的三个练习（p.21–23）

p.21 要偶数长度，可把任意两位打包：$((0+1)(0+1))^{\ast}$。每轮正好两位，零轮是长度零；任意偶数长串也能从左到右两位一组。

p.22 要“不以01结尾”，要把长度不足2的串另外照顾：

最后两位只有四种，排除01，保留另三种；这一分类只适用于长度至少2，故前面的三个短串不能省。

p.23 要0的个数为奇数，可写 $1^{\ast}01^{\ast}(01^{\ast}01^{\ast})^{\ast}$。开头贡献一个0，每轮再贡献两个；每个间隙用任意1填满，因而没有额外限制1的位置。比如三个0被分成第一0加一对0，而不是要求三个0连续。

本部分小测的完整解法（p.24–25）

p.24 在字母表 $\{a,b,c\}$ 上恰好一个 a：$(b+c)^{\ast}a(b+c)^{\ast}$。左右不准再出现 a，中间强制一次，两个条件缺一不可。

题面（本讲 · Short Quiz 7、8 · p.25；图片，视觉读取；公式按原题重排）

p.25 7. Find a regular expression for the set $\{a^n b^m:n\ge3,m\text{ is odd}\}$.

8. Find a regular expression for the set $\{a^n b^m:(n+m)\text{ is odd}\}$.

第7题先放三个 a，剩余 a 任意；b 先放一个，再成对增加，得 $aaaa^{\ast}b(bb)^{\ast}$。最短串 aaab 满足条件；省掉前三个 a 就会错误接纳 ab。

第8题把总数奇数分成互斥的两类：a 奇 b 偶，或 a 偶 b 奇。得

第一项的计数为 $(2i+1,2j)$，第二项为 $(2i,2j+1)$，总和都奇数；每个总和奇数的整数对又必属于其中一类。注意串仍须先全 a 后全 b，不能用“任意奇数长串”替代。

考试角度：（C 级 通识）常见考法是给计数或后缀条件写 RE，再用空串和最短边界串检查是否误接纳。

考试角度：（A 级：HW02-2025T1-题目-更新.pdf Q2，考的是精确出现次数和至少一次。）见附录 A1。

考试角度：（A 级：期中练习-含解答-学期待核.pdf Q1(9–10)、Q3；期末-2022T1-资料包.pdf Q2，对应表达式语法、奇偶与分块；扫描卷题面经视觉读取，练习卷不冒称正式考卷。）见附录 A2。

本讲核心考点

• RE 的递归语法和语言语义（p.7–11，C 级）。
• 并、连接、闭包及优先级（p.12–17，C 级）。
• 边界串、奇偶与最短长度条件（p.21–25，C 级）。

附录

本部分没有需要另列的推导；定义与算例在相应页段内。

A1 作业/往年题演练（非讲义内容）：精确出现次数和至少一次

题面块（HW02-2025T1-题目-更新.pdf（本地课件） · Q2 · p.1）：

p.1 (20pts) Give regular expressions for the following languages on $\Sigma=\{a,b,c\}$:

p.1 1) All strings containing exactly two a’s.

p.1 2) All strings that contain at least one occurrence of each symbol in $\Sigma$.

1）$(b+c)^{\star}a(b+c)^{\star}a(b+c)^{\star}$。三个间隙禁a，两个固定a保证恰好两次。baac可按b / a / λ / a / c拆开；aaa无法放入三个禁a间隙。

2）记R=(a+b+c)，只是书写缩写。取 $R^{\star}(aR^{\star}bR^{\star}c+bR^{\star}aR^{\star}c+aR^{\star}cR^{\star}b+cR^{\star}aR^{\star}b+bR^{\star}cR^{\star}a+cR^{\star}bR^{\star}a)R^{\star}$。六项列出a、b、c被选作见证位置的六种先后顺序。每项显然含三字符；任何目标串取三种字符的首次出现，必落某一排列。间隙允许任意字符，因此不错误限制每种只能出现一次。ccbaa可选c,b,a排列，aaab缺c则没有分支匹配。

回到正文：精确出现次数和至少一次

A2 作业/往年题演练（非讲义内容）：表达式语法、奇偶与分块

题面块（期中练习-含解答-学期待核.pdf（本地课件） · Q1(9–10) · p.1；按原图保留括号）：

p.1 9. The string $((\emptyset+\lambda)\emptyset)^{\star}$ is not a valid regular expression.

p.1 10. The language of the regular expression $(1+01)^{\star}$ is the set of all binary strings with no substring 00 and that do not end with 0.

9为False：空集、空串是基本表达式，并、拼接、星均合法。内部先得{λ}拼空集=空集，最外星得{λ}，不是语法无效。10为True：每个0都在01块中；反向任何无00且不以0结尾的串，每个0后必接1，可从左按01或单1切块，λ由零块接受。

题面块（同文件 · Q3 · p.3）：

p.3 1) Give a regular expression for the language on $\Sigma=\{a,b,c\}$: all strings containing exactly one a.

p.3 2) Find a regular expression for the set $\{a^n b^m:n\geq3,m\text{ is odd}\}$.

p.3 3) Find a regular expression for the set $\{a^n b^m:(n+m)\text{ is odd}\}$.

1为 $(b+c)^{\star}a(b+c)^{\star}$，两侧不能再藏a。2为 $aaa\,a^{\star}b(bb)^{\star}$，固定三个a保证下界，b加任意对b保证正奇数。3为 $a(aa)^{\star}(bb)^{\star}+(aa)^{\star}b(bb)^{\star}$，分别为a奇b偶、a偶b奇，且始终保持a段在前。检查a、b、aab都属于第3式，ab长度2不属于。

题面块（期末-2022T1-资料包.pdf（本地课件） · Q2 · p.2，扫描件视觉读取；公式重排）：

p.2 Give a regular expression for the following language. $L=\{w\in\{a,b\}^{\star}:\text{The numbers of a's and b's in w have different parity}\}$.

p.2 Recall that two integers have different parity if one is odd and the other is even. For example, bab ∈ L and ab ∉ L. Briefly justify your answer.

不同奇偶当且仅当计数总和即串长为奇数，因此式为 $(a+b)((a+b)(a+b))^{\star}$。先任意一字，再任意多对字，正好奇数长；这里没有a在b前的限制，不能套上一题第3式。bab按b·ab匹配，ab不能分成1加偶数长。

回到正文：表达式语法、奇偶与分块

来源与证据

历史版本考试证据（本次未重新读取全部试卷）：读了 HW01-2025T1-题目.pdf、HW01-2026T1-题目.pdf、HW02-2025T1-题目-更新.pdf、HW03-2025T1-题目.pdf、HW04-2025T1-题目.pdf、HW05-2025T1-题目.pdf、期中练习-含解答-学期待核.pdf、期末-2022T1-资料包.pdf、Final-Exam-2023T1-题目.pdf、Final-Exam-2024T1-题目.pdf、Final-Exam-2025T1-题目.pdf、期末-2023T1-资料包.pdf、期末-2024未核-资料包.pdf；未识别用途的 PDF：无

• 原件：L03-正则表达式-资料包.pdf（本地课件），PDF p.1–25。

• 本次独立学习修订：逐页核对本讲 PDF 文本，视觉核对 p.25、31、36–38、42、44–45、49–50、53–54、102–104 的图和题面；原图以边表和逐步计算展开，未发布原件截图。