CSCI3130 L03 Part 2 表达式与自动机

课程：CSCI3130 Formal Languages and Automata Theory · 资料包，学期待核 本讲：L03 Part 2 表达式与自动机 · 原件 L03-正则表达式-资料包.pdf（本地课件） p.26–54 定位：用构造证明 RE 与有限自动机表达能力相同。 前后：上一份 L03-P1-正则表达式.md · 下一份 L03-P3-正则文法.md

p.26 Outline，进入正则表达式与有限自动机的等价性。

等价定理必须证明两个方向（p.27–29）【新】

p.27 For every regular language there is a regular expression

p.27 的 Kleene 定理说的是两种工具描述的语言类相同。p.28 要把任意 RE 变成接受相同语言的 NFA；p.29 要从任意有限自动机造回 RE。只做一个方向，只能说明一个语言类包含另一个，不能推出等价。

归纳从表达式的结构出发（p.30–32）

p.30 Proof by induction on the size of r

p.30 不是对输入串长度归纳，而是对 RE 的有限构造过程归纳。p.31 的三幅图从左至右都是起点与终点：表示空语言的两点不连通；表示空串的两点以空边连接；表示单字母语言的两点以该字母连接。三个基本构件都有有限机器。p.32 假设两个较小 RE 已有对应机器，下一步只需说明合成表达式也有机器。

把语义运算变成接线（p.33–35）

p.33 列出并、连接、星号和括号四种构造；p.34 把它们解释成语言运算。括号不改变集合，另三项各需要一个构造。p.35 用单终态 NFA 当模块：可添加一个新终态，用空边从旧终态接入，并取消旧终态资格。这里是“存在一台等价的单终态机器”，不是“每台 NFA 原本就只有一个终态”。

并、连接、星号的图（p.36–38）

图（p.36）：新起点以两条空边分叉到两个模块，模块出口再合流到新终点。元素：原模块的状态必须先改成不相交的名字。看什么：一条接受路径完整走其中一个模块，故表示并；不能中途跳模块。

图（p.37）：两个模块依次串接。元素：第一模块出口到第二模块入口的边标空串。看什么：读完第一段才能开始第二段，故整串可以切成两个语言里的串；切分不必唯一。

图（p.38）：入口可直接绕到出口，也可穿过模块，出口还有返回入口的空边。看什么：绕行保证零次重复，返回保证任意有限次重复；漏前一条会变成至少一次。图中的循环不要求永远循环，NFA 接受只要求存在一条有限接受路径。

归纳收尾（p.39–41）

p.39 由刚才的具体构造得到并、连接、星号保持正则性。p.40 将三个结论代回表达式语义。p.41 补上括号不改变语言，四种构造全部完成，因而每个有限构成的 RE 都能转 NFA。不要只引用“正则语言封闭”而不解释封闭性从哪里来；这里构造本身就是证据。

把模块组合跑一次（p.42–44）

题面（本讲 · Example 3.7 · p.42；公式按讲义重排）

p.42 Find an NFA that accepts L(r), where $r=(a+bb)^{\ast}(ba^{\ast}+\lambda)$.

图上第一模块选择 a 或两个 b，外接星号；第二模块选择一个 b 后任意 a，或空串；最后连接。为把图读成能执行的机器，给同语言的简化状态命名：s 为初态，s 读 a 回 s，读 b 到 t，t 读 b 回 s；s 空转到 u，u 读 b 到 v，v 读 a 回 v；u、v 均为终态。s、t 负责前半段，u、v 负责后半段。这样空串经 s→u 接受；b 经 s→u→v 接受；bb 可在 s→t→s 后再空转接受。这些名字是解释用，不是原图标签。

原图逐条接线（p.42）：为阅读未标名的圆圈，以下按从左到右临时命名，保留原图拓扑。M1 的入口 x 经 a 到出口 z，另一路 x 经 b 到 y，再经 b 到 z；M2 的入口 u 经 b 到 v，v 上有 a 自环，v 经 λ 到出口 w，u 也可经 λ 直接到 w。然后加星号入口 s、出口 t，以及全机终点 f。完整边表如下，表外无转移：

只有 s 是全机初态，只有 f 是全机终态；模块原来的双圈在接线后取消终态身份。例串 bbbaa 的一条接受路线是 s→x→y→z→t→u→v→v→v→w→f，消费的字符依次是 b,b,b,a,a，其余都是空边。这与上面的简化图是同一语言的两种实现。

p.43 开始反向构造：把所有起点到终点的路径标签压成 RE，不能逐一列无限多条路径。p.44 的 GTG 允许整条边标 RE，并行的 a、b 边合成 $a+b$。图左、右两点都为终态，左点有 a 自环，右点有 c 自环，所以语言还包含停在左点的 $a^{\ast}$；完整为 $a^{\ast}+a^{\ast}(a+b)c^{\ast}$。漏看初态的双圈就会漏掉空串和纯 a 串。

消去中间状态（p.45–47）【新】

p.45 图：初态 $q_0$ 读 b 到 $q_1$；$q_1$ 有 b 自环，读 a 可回 $q_0$，读 a 或 b 可到唯一终态 $q_2$；$q_2$ 有 b 自环。p.46 删除 $q_1$ 时，原来经它的路径必须留下来：回到 $q_0$ 是“b进去，若干b循环，a出来”，标签 $bb^{\ast}a$；走到 $q_2$ 是 $bb^{\ast}(a+b)$。

p.47 因而得到 $(bb^{\ast}a)^{\ast}bb^{\ast}(a+b)b^{\ast}$。前面可反复回起点，中间恰一次进入终点，最后只在终点循环。最短接受串 ba、bb 都可由中间项得到；单 b 只到中间状态，不接受。

两状态公式与四条新边（p.48–50）

p.48 为方便统一运算，把缺边标成 $\varnothing$；这仍表示不能走，不是免费空边。n 个状态包含自环共有 $n^2$ 对有序端点。

p.49 图仅左点是起点、右点是终点。左自环 $r_1$，左到右 $r_2$，右到左 $r_3$，右自环 $r_4$，所以

先在左侧循环再首次到右侧；之后每一轮要么右侧自环，要么返回左侧再回来。p.50 删除 $q_2$，四条新标签分别是 $e+af^{\ast}b$、$h+af^{\ast}c$、$i+df^{\ast}b$、$g+df^{\ast}c$。例如第一条含直接自环 e，或经 a 到中间、循环 f 若干次、再沿 b 回来；加号是保留两种可能。将这四条依次替代 $r_1,r_2,r_3,r_4$ 就得到完整结果，无须硬展开巨大式子。

从一条被删除的路径读出四因子（补充自取例）：设 p→q 原标签为 d，p→k 标签为 a，k 自环为 b，k→q 标签为 c。经 k 的路径可读 ac、abc、abbc，即先 a 进入、在 k 上读零个或多个 b、最后 c 离开；新边因此是 $d+ab^{\ast}c$。ac 说明星号必须允许零圈，d 说明不能删掉旧边，而 a 或 ab 都还没有到 q，不能混入。

算法的不变量可说得更精确：已消去某些状态后，一条保留边表示端点之间、内部只经过那些已消去状态的全部路径标签。下一轮把 k 加入允许的内部状态：要么从不经过 k，要么先到 k、在 k 处绕有限次、最后离开。这正是旧边加三段连接的原因。有限次消点保证过程终止；表达式可能膨胀，但不影响“有有限表示”的证明。

一般状态消去算法（p.51–52）

p.52 Repeat step 2 to 4 until the correct RE is obtained.

消去 k 时，对每对保留状态 p、q，同时更新为

旧边留下不经 k 的走法，新增项留下最后一次局部穿越 k 的走法。每轮更新应使用删除前的标签，不能半更新半读新值。之后才删 k 的点和边。用 $r+\varnothing=r$、$r\varnothing=\varnothing$、$\varnothing^{\ast}=\lambda$ 化简。若初终态重合，先添独立新起点、新终点及必要空边，不能不检查条件就套“两点”公式。

偶数 a、奇数 b 的完整表达式（p.53–54）

题面（本讲 · Example 3.11 · p.53；公式按讲义重排）

p.53 Find an RE for the language $L=\{w\in\{a,b\}^{\ast}:n_a(w)\text{ is even and }n_b(w)\text{ is odd}\}$.

图有 EE、OE、EO、OO 四种奇偶状态，初态 EE，唯一终态 EO。a 切换第一位、b 切换第二位。p.53 删除 OE 后，EE 自环 aa，OO 自环 bb，EE→OO 为 ab，OO→EE 为 ba；EE 与 EO 间都是 b，OO 与 EO 间都是 a。p.54 再删 OO，令

再删 OO 时四条边的计算不能只背结果：EE→EE 原有 aa，新增 EE→OO 的 ab、OO 自环 bb 任意轮、OO→EE 的 ba，得 A；EE→EO 原有 b，新增 ab、任意轮 bb、a，得 B；EO→EE 原有 b，新增 a、任意轮 bb、ba，得 C；EO 自环原为 ∅，新增 a、任意轮 bb、a，得 D。每条更新都在同一张删除前的图上读取旧标签。

最终 RE 为 $A^{\ast}B(D+CA^{\ast}B)^{\ast}$。A、D 是两个自环，B、C 是双向边，正好代入 p.49 的公式。空串必须先过 B 才可能接受，而 B 每个分支都含字母，故拒绝空串；b 取 B 的第一项直接接受；aab 取 A=aa 后 B=b 接受；ab 到 OO 被拒绝。完整逐项替换见附录 A1。

考试角度：（C 级 通识）常见考法是消去指定状态并写更新后的四条标签；旧边、循环星号、空边与空语言各是独立的失分点。

考试角度：（A 级：HW02-2025T1-题目-更新.pdf Q3，考的是表达式转DFA及交语言简化。）见附录 A2。

本讲核心考点

• RE 到 NFA 的结构归纳（p.30–41，C 级）。
• GTG 标签与状态消去（p.44–52，C 级）。
• 奇偶自动机完整转 RE（p.53–54，C 级）。

附录

A1 两次消去的逐项替换

第一次消去 OE。它没有非空自环，故循环标签 $\varnothing^{\ast}=\lambda$。EE→EE 从 $\varnothing+a\lambda a$ 得 aa；EE→OO 从 $\varnothing+a\lambda b$ 得 ab；OO→EE 从 $\varnothing+b\lambda a$ 得 ba；OO→OO 从 $\varnothing+b\lambda b$ 得 bb。OE 与 EO 之间缺边，因此经 OE 的新增项含空语言，不改变 EO 的边。

第二次消去 OO。EE→EE 是旧 aa 加经 OO 的 $ab(bb)^{\ast}ba$，得 A。EE→EO 是旧 b 加 $ab(bb)^{\ast}a$，得 B。EO→EE 是旧 b 加 $a(bb)^{\ast}ba$，得 C。EO→EO 是旧空语言加 $a(bb)^{\ast}a$，得 D。两状态间所有有限接受路径按“初次到 EO＋零次或多次回到 EO”分类，得到 $A^{\ast}B(D+CA^{\ast}B)^{\ast}$。每次替换保留恰好同一组路径标签，因此不只几个试串正确，而是整个语言相等。

回到正文

A2 作业/往年题演练（非讲义内容）：表达式转DFA及交语言简化

题面块（HW02-2025T1-题目-更新.pdf（本地课件） · Q3 · p.1；公式按原件重排）：

p.1 (20pts) Find DFA’s that accept the following languages ($\Sigma=\{a,b\}$):

p.1 1) $L(ba(a+ba)^{\star}(b+bb))$.

p.1 2) $L((a^{\star}b)^{\star}a)\cap L(b^{\star}ab^{\star})$.

1）先固定ba前缀，到循环边界C；循环可读a或ba，最后读b或bb。完整DFA：

F1表示刚读到的b可以是结尾，也可等a完成下一循环块；F2表示末尾bb已读完不能再延续。bab接受，babb接受，baba拒绝但babab接受；这些检查涵盖循环与终结的冲突位置。

2）第一语言必以a结尾，第二语言恰有一个a，因此交串只能为若干b后接一个a。反向任意bᵏa可在第一式选k个a星取空的b块，在第二式选后方b星为空，所以交恰为 $b^{\star}a$。DFA三态s、F、D：s读b留s、读a到F；F读a/b到D；D读a/b留D；仅F终态。λ拒绝、a与bba接受、ab拒绝。

回到正文：表达式转DFA及交语言简化

来源与证据

历史版本考试证据（本次未重新读取全部试卷）：读了 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.26–54。

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