CSCI3130 L04 Part 1 封闭性质

课程：CSCI3130 Formal Languages and Automata Theory · 资料包，学期待核本讲：L04 Part 1 封闭性质 · 原件 L04-正则语言性质-资料包.pdf（本地课件） p.1–32 定位：用接线、乘积状态和集合运算构造新的正则语言。前后：下一份 L04-P2-判定问题.md

p.1 标题页；p.2 Outline。本讲分封闭性、可判定问题、非正则证明；p.102–103 是另列的尾段小测。

本讲导航

P1 封闭性质：p.1–32。
P2 判定问题：p.33–44。
P3 非正则语言：p.45–101。
P4 结尾小测：p.102–103。

封闭性到底承诺什么（p.3–5）【新】

p.4 We say: Regular languages are closed under

p.3–4 列出并、连接、闭包、反转、补、交和差。封闭性的前提是输入语言已经正则，结论是运算结果仍正则；没有说任意非正则语言参与运算也能得到同样结论。p.5 为两个输入语言取单终态 NFA 作模块，接线构造将把集合运算变成机器。

并操作允许选任一分支（p.6–8）

p.6 两个例子为 $L_1=\{a^nb:n\ge0\}$ 和 $L_2=\{ba\}$ 。p.7 图的新起点通过空边任选一台机器，旧终点再连新终点；接受路径选哪支，就说明串属于哪一个集合。p.8 代入例子，b、ab、aab 来自第一支，ba 来自第二支；空串不属于任一支，也不会因为新空边而凭空被接受。

连接与零次重复（p.9–11）

p.9 图把前一机器出口空接后一入口；p.10 的语言变成 $\{a^nbba:n\ge0\}$ ，因为每次都要先读一个 $a^nb$ 再读 ba。取 n=0 得 bba，n=1 得 abba；这不是两语言的交集，也不能交换两段次序。p.11 星号构造加回路以便重复完整模块，并加直达空边允许零次重复，故空串必在 $L_1^{\ast}$ 。

反转的是串内顺序（p.12–14）

p.12 中星号的一串可以切为若干 $a^nb$ 块，各块 n 可不同，不要求所有轮数相同。p.13 反转构造把每条边方向倒过来并交换初终态；有多个终态时先统一为一个终态或用新起点空边连接。p.14 的 $a^nb$ 反转为 $ba^n$ ：原来最后读的 b 现在最先读，而不是把字母改名。接受路径一一倒转，给出两个方向的对应。

补运算必须用完整 DFA（p.15–16）

p.15 Take the DFA that accepts L1

p.15 对 DFA 翻转终态资格。为何强调 DFA：每个串都恰有一个最终状态，原来接受的恰好变拒绝；NFA“存在接受分支”的条件不受逐状态翻转正确取反。p.16 图为 $a^{\ast}b$ 补上死状态，再翻转，得到 $\{a,b\}^{\ast}\setminus\{a^nb:n\ge0\}$ 。空串原本拒绝，取补后接受；ab 原本接受，取补后拒绝；abb 原本走死状态，取补后接受。遗漏死状态会漏掉 abb 这类串。

直接给 NFA 翻双圈为什么失败（补充自取反例）：设初态 s 在 a 上可以到终态 f，也可以到非终态 r，f、r 都无出边。原机接受 a，因为存在到 f 的完整运行。把全部终态资格翻转后，r 变终态，所以新机仍接受 a；而真正的补语言必须拒绝 a。这里“至少一条接受”的否定是“每条都不接受”，不是“至少一条不接受”。完整 DFA 每串只有一个最终状态，才让这两种逻辑在单一结果上吻合。

同时跑两台机器（p.17–19）【新】

题面（本讲 · p.17；集合公式按讲义重排）

p.17 Let's step through an example

$L_1=\{x\mid00\text{ is not a substring of }x\}$

$L_2=\{x\mid x\text{ ends in }01\}$

图中第一机器 A 为没违规且不以0结束，B 为没违规且以0结束，C 为已出现00；A、B 双圈。第二机器 X 为无有效后缀，Y 为以0结束，Z 为以01结束，只有 Z 双圈。p.18 初态分别 A、X；p.19 乘积状态写 AX 等，表示读了同一个前缀后两台机分别在哪。状态总数至多 $3\times3=9$ ，不是两台轮流各读一位。

逐位推进乘积状态（p.20–22）

p.20 对 AX 读0，第一台 A→B，第二台 X→Y，所以到 BY；读1，两台都保持起点，所以回 AX。p.21 展开所有可达状态，下表按图得到六个可达点：

状态	读0	读1
AX	BY	AX
BY	CY	AZ
AZ	BY	AX
CY	CY	CZ
CZ	CY	CX
CX	CY	CX

AY、BX、BZ 从初态到不了，可去掉。p.22 接受条件决定运算：交要求两分量都接受，差要求第一接受且第二不接受。转移表不变，只改终态集合。

交、差、并各选哪些终态（p.23–25）

p.23 交集的可达终态只有 AZ：没有00而且以01结尾。01 走 AX→BY→AZ 接受，001 走 AX→BY→CY→CZ 拒绝，因为虽以01结尾，却已经含00。

p.24 差集可达终态 AX、BY：没有00但不以01结尾；空串停 AX 接受，01 到 AZ 拒绝。p.25 并集可达终态 AX、BY、AZ、CZ：至少一台接受。001 到 CZ 虽不满足第一条件，却满足第二条件，因此接受。三个图的区别只在双圈，不在边方向。

用集合恒等式推出封闭（p.26–28）

p.26 原图含三条补线，不能依据文本抽取丢掉的横线读公式。正确重排为

L_1\cap L_2=\overline{\overline{L_1}\cup\overline{L_2}}.

已有补、并的封闭性，于是交也封闭。p.27 的 $\{a^nb:n\ge0\}\cap\{ab,ba\}=\{ab\}$ ：ba 不属于第一集合，b 不属于第二集合。p.28 差集为 $L_1\cap\overline{L_2}$ ，仍是已经证明封闭的两种运算组成。所有补运算要相对于同一个字母表的全集。

同态是逐字母替换（p.29–31）【新】

p.29 a homomorphism is a substitution in which a single letter is replaced with a string.

p.29 的 $h:\Sigma\to\Gamma^{\ast}$ 为每个输入字母固定一个输出串，然后保持连接次序扩展到整串。p.30 规定 h(a)=ab、h(b)=bbc，故 h(aba)=ab·bbc·ab=abbbcab，h(aa)=abab，因此集合的像为 $\{abab,abbbcab\}$ 。同一个 a 每次都用同一替换，不能依位置另作选择。

p.31 的 h(a)=dbcc、h(b)=bdc 作用在 $(a+b^{\ast})(aa)^{\ast}$ ，得到 $(dbcc+(bdc)^{\ast})(dbccdbcc)^{\ast}$ 。替换串外的括号不可漏，否则原来重复一个 b，会错误变成只重复输出串的最后字母。

为什么同态像仍正则（p.32）

p.32 Let h be a homomorphism. If L is a regular language, then its homomorphic image h(L) is also regular.

用 L 的 RE，把每个字母 a 换成表示 h(a) 的有限串；并、连接、星号结构全部保留。替换后仍是一个有限 RE，所以语言正则。若某字母被映为空串，同样用 $\lambda$ 作合法基本表达式，不会破坏论证。

考试角度：（C 级通识）常见考法是选合适表示来证明封闭，或指出对 NFA 直接翻转终态为什么不是补集构造。

考试角度：（A 级：期中练习-含解答-学期待核.pdf Q1(6)，对应正则交补封闭判断；扫描卷题面经视觉读取，练习卷不冒称正式考卷。）见附录 A1。

自检：两个非正则语言的并，一定非正则吗？

封闭定理的前提是哪一类语言？尝试一个语言与它的补。

展开推理与答案

不一定。若 L 非正则，则它的补也非正则，否则由正则补封闭性会推出 L 正则。但两者之并为 $\Sigma^{\ast}$ ，它是正则语言。封闭定理不能把“两个输入正则”倒过来推成“输入非正则则输出非正则”。

把原图变成可执行的两张输入表（p.16–18）

p.16 用 s 表示左侧初态，f 表示中间终态，d 表示右侧死状态。转移为 s 读 a 留 s、读 b 到 f；f 读 a 或 b 均到 d；d 读任意字母留 d。原机终态为 {f}，补机终态为 {s,d}。每个串读完只有一个位置，所以逐个翻转接受性确实覆盖全集。

p.17–18 的乘积构造依赖下面两张原始表。这样不必对着箭头猜：

第一台状态	读0	读1	接受
A（初态）	B	A	是
B	C	A	是
C	C	C	否

第二台状态	读0	读1	接受
X（初态）	Y	X	否
Y	Y	Z	否
Z	Y	X	是

可达表中每格都可由它们独立算出，例如 CZ 读1得到 CX。去掉 AY、BX、BZ 的依据是不可达，不是这些状态“不接受”。

本讲核心考点

补集需要完整 DFA（p.15–16，C 级）。
乘积机的转移与终态条件（p.17–25，C 级）。
德摩根律与差集（p.26–28，C 级）。
同态替换及其封闭性（p.29–32，C 级）。

附录

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

A1 作业/往年题演练（非讲义内容）：正则交补封闭判断

题面块（期中练习-含解答-学期待核.pdf（本地课件） · Q1(6) · p.1）：

p.1 6. The class of regular languages is closed under intersection and complement.

True。交使用两台DFA状态乘积，终态要求两分量同时接受；补先使DFA在共同字母表上完整，再交换终/非终态。若原图漏读b的转移，仅交换双圈会错误漏掉本应在补语言中的b，所以“完整”是构造条件。练习题未注明学期，不作当前考试安排依据。

回到正文：正则交补封闭判断

来源与证据

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

原件：L04-正则语言性质-资料包.pdf（本地课件），PDF p.1–32。
本次独立学习修订：核对本讲全部103页的文本，视觉复核 p.16–17、21、26、42、54–56、102–103；图示以表格、轨迹和证明展开。