CSCI3130 L02 Part 3/4 Equivalence of DFA and NFA

课程：CSCI3130 Formal Languages and Automata Theory · 2026T1（沿用既有原件版本标记） 本讲：L02 Part 3/4 Equivalence of DFA and NFA · 原件 lec2.pdf（本地课件） p.159–201 定位：把一组NFA可能状态看成一个DFA状态，实际完成子集构造，并用不变式证明这种压缩既不漏收也不多收字符串。 前后：上一份 L02-P2-非确定有限自动机.md · 下一份 L02-P4-状态最小化.md

p.159 Outline 分节页。

Equivalence of DFA and NFA

等价比较的是语言（p.160–162）【新】

p.160 Two finite accepters M1 and M2 are said to be equivalent if $L(M_1)=L(M_2)$

公式按讲义重排。p.160 只比较每个输入的接受结果，不要求状态数、名称或运行路径一样。p.161 的NFA用q0读1到q1、q1读0回q0，初态q0也是唯一终态；完整DFA额外增加陷阱q2，让q0读0、q1读1均到q2，再在0、1上自环。两者都接受 $\{10\}^{\ast}$：空串、10、1010；单1和11都拒绝，尽管拒绝的具体机制不同。

p.162 明确“more powerful”是能识别别的同类机器完全不能识别的语言。少用几个状态并不自动表示能力更强；NFA的描述可能更简洁，但本部分将证明与DFA的语言类相同。

相等需要两个包含方向（p.163–165）

p.163 提出NFA语言族等于正则语言族；p.164 的方向容易：把DFA的唯一后继q换成单元素集合 $\{q\}$，不加lambda边，就得到等价NFA。p.165 的困难方向是将任意NFA转换为等价DFA，而非只展示一两个成功转换的例子。

补充：两个模型均能识别某些共同例子只证明交集非空；只有“任意一台都可转换”的统一方法才能证明语言族包含。

子集构造的第一行（p.166–168）【新】

图（p.166）：待转换的三状态NFA。 元素：初态q0，唯一终态q1；q0读a到q1，q1读a自环、lambda到q2，q2读b回q0，其他边为空。 看什么：到q1后不消费字符也可到q2，因此DFA状态要同时保存这两个可能位置。

p.166 初始集合A为 $\{q_0\}$，因为q0没有lambda出边；p.167 A读a先到q1，再做空闭包得到 $B=\{q_1,q_2\}$；p.168 A读b无路可走，得到DFA状态 $D=\varnothing$。空集在DFA里是一个具体状态，含义为“全部NFA分支都失败了”，不是应删掉的空格。

完成可达状态表（p.169–171）

p.169 B读a：q1可到q1，q2无a边，再补lambda可达q2，因此仍B。p.170 B读b：只有q2能读b到q0，得到A。p.171 空集读任意字符仍为空集，所以补D上的两个自环。至此每个可达集合、每种字母都有唯一后继。

标终态与状态上界（p.172–174）

p.172 B画双圈，因为包含原终态q1，A与D不包含。算aaba：A→B→B→A→B，接受；aabb：A→B→B→A→D，拒绝。p.173 再说明目标为同语言。p.174 指出新状态来自 $2^Q$：若原NFA有n态，最多 $2^n$ 个子集，实际只需可达的那些。本例 $2^3=8$ 是上界，真正只出现3个集合，不能为了凑满8态把不可达子集全部当必需状态。

初态为什么要注意空闭包（p.175–177）

p.175 写DFA初态为 $\{q_0\}$，p.176 在本例确实正确，因为q0没有lambda出边。补充，通用条件：一般初态应为 $C(\{q_0\})$，其中C取零步或多步lambda可达的全部状态。若q0能空走到某终态却只保留q0，便会错误拒绝空串；不能把本例的简化直接推广到所有NFA。

p.177 对集合中每个原状态计算读a后的所有可达位置，再取并集。采用始终lambda闭合的状态集合S时，可统一写

$\delta$ 是原NFA单步函数，$\Delta$ 是新DFA函数。并集不会“选择其中一条分支”，而是将所有候选位置一起保存。

为什么算法会停（p.178–180）

p.178 演示 $\Delta(\{q_0\},a)=\{q_1,q_2\}$；p.179 要求对全部字母重复，直到再没有新转移；p.180 得到前面的三态完整图。有限Q意味着可能子集有限，每个集合只处理一次，故算法会终止。

取初态的空闭包，放入待处理集合
每次取一个尚未处理的状态集合 S
  对每个输入字符 a
    从 S 中所有状态沿 a 边走一步，合并后继
    计算后继的空闭包 T
    记录 S 在 a 上到 T
    若 T 从未出现，加入待处理集合
直到所有出现过的集合都处理完

子集状态不是一组会互相传送的机器位置（补充）：{q1,q2} 的含义是“有一条运行到 q1，另有一条运行到 q2”，不是某一条运行可以无条件从 q1 跳去 q2。下一字符的后继必须分别来自原图真实存在的边。反向正确性之所以成立，就靠每个集合成员始终保留这样的路径见证。

手工建表时可给每个集合先排序，再起短名 A、B、C。{q1,q2} 与 {q2,q1} 是同一状态；重复到达应复用同名，不能新增另一行。处理队列里每行要补齐所有字母，即使后继为空也记作空子集状态。这样“已发现”“待展开”“已展开”三种工作状态明确，既不会漏边，也不会因自环一直重复展开。

新终态必须“至少包含一个”（p.181–182）

p.181 If some $q_j$ is a final state in the NFA

公式按讲义重排。新终态条件为 $S\cap F\ne\varnothing$。p.182 的B既含终态q1又含非终态q2，仍必须双圈；若要求集合中每个状态都是终态，便把NFA的存在量词错误改为全称。

第二个完整例子（p.183–184）

图（p.183）：三状态NFA。 元素：初态q0，唯一终态q1；q0在0上自环，q0读0或1还可到q1；q1读0或1到q2；q2在1上自环，无其他边。 看什么：q0的0边有两个后继，是子集状态产生的起点。

p.183 先展开几层；p.184 画出完整七个可达状态，下表逐格列出同一结果。含q1的B、C、D、E为终态，A、F、X非终态。

例如B读0：q0贡献q0、q1，q1贡献q2，合并成D。E读1：q1与q2都贡献q2，集合去重后只有F，不能把同一个状态算两遍。输入001走A→B→D→E接受；010走A→B→E→F拒绝。实际上唯一终态q1必须是运行最后一步才到达，所以接受的是若干0后接任意一个位；继续多走进入q2就不接受。

正确性证明的目标（p.185–187）

p.185 的Theorem 2.2说转换前后语言相同。p.186 拆成两个包含，p.187 先任取原NFA接受的w，而不是固定某个例串。补充，统一不变式：读完任意前缀u，新DFA所处集合恰好是原NFA读u可达的全部状态。证明“恰好”同时排除漏掉可达状态和加入不可达状态。

成功路径必须被保留（p.188–190）

p.188 从NFA的一条成功运行取最后终态qf；p.189 要证明DFA最终集合含qf；p.190 推广到任意前缀的任意可达状态qm。每读一个字符，DFA对当前集合的每一成员都取后继，故成功路径不可能因为分支很多而被丢掉。图中的单条NFA路径只是一个见证，DFA集合还可以同时含其他路径的状态。

归纳基础和假设（p.191–193）

p.191 从长度1描述归纳基础，p.192 假设长度不超过k成立，p.193 将长度k+1串拆成前缀与最后一个字符。补充：含空串的完整证明还要先核长度0：DFA初态就是原初态的空闭包，恰好等于读取零个字符的可达集合。这个基础也解释了p.175一般化时为什么必须补空闭包。

两个方向都不能省（p.194–196）

p.194 将归纳假设的集合沿最后字符扩展；p.195 因最终集合含NFA终态，DFA接受。p.196 把反方向标成“proof is similar”，但反方向承担防止多收的工作：若DFA最终集合含终态，那么该状态必须来自上一集合中的某个真实可达状态的一次合法字符转移，再接合法空转移；逐层追溯可拼出NFA成功运行。完整双向归纳见附录 A1。

将 p.191–196 的双向归纳留在主线：令 R(u) 是 NFA 读完 u 并允许空移动后所有可达状态，D(u) 是所构造 DFA 读完 u 的集合状态。要证每个 u 都有 $D(u)=R(u)$。

基础：u 是空串时，两者都是原初态的空闭包。归纳假设：对前缀 u，两集合相等。现在追加字符 a。

先取任意 $r\in R(ua)$。到 r 的真实路径在消费最后一个 a 之前，停在某个 $p\in R(u)$；沿原图 a 边到 t，再经空边到 r。由假设，p 也在 D(u) 中。新机对集合每个成员取 a 后继并补空闭包，所以必加入 t 和 r，得到 $R(ua)\subseteq D(ua)$。

反过来取任意 $r\in D(ua)$。按新转移的定义，r 必来自某个 $p\in D(u)$ 的真实 a 边及随后的空路径。归纳假设提供原机读 u 到 p 的路径；把这段与 a 边、空路径接起来，就证明 r 在 R(ua) 中。因此 $D(ua)\subseteq R(ua)$。

归纳得到集合相等后，两机器都以“集合与 F 非空相交”判断接受，于是所有输入的结果一致。这既补齐课件省略的反向证明，也覆盖长度0的基础；附录保留完整形式作为可选重复阅读。

同一语言族与单一终态（p.197–198）【新】

p.197 总结NFA接受的正是正则语言。p.198 问任意NFA能否转换成只有一个终态的等价NFA。这不是DFA最小化，也不是把原所有终态直接合并；合并可能凭空允许从一个旧终态接另一个的出边。

题面（lec2.pdf · Exercise 2.3.7 · p.198）

p.198 Any NFA can be converted to an equivalent NFA with a single final state

用新的结束节点保留所有路径（p.199–201）

p.199 原例初态s，两个终态u、v，另一个非终态t；边s读a到u、读b到v、u读b到t、t读a回s。新增f，将u、v改成非终态，并各加lambda边到f，f为唯一终态且无出边。旧转移原样保留，因此可继续从u经过t回s的旧路径也仍在。

p.200 将方法推广到任意多个旧终态，每个旧终态都可在输入恰好结束时空走到f。若原机器接受w，沿旧成功运行到旧终态再空走到f，新机接受；若新机接受，最后一步必由某旧终态空走到f，去掉此步就得到旧机成功运行。

p.201 特别处理原F为空：新增一个不可达终态f，不连任何入边。旧机接受空语言，新机也没有输入能到f，仍接受空语言。不要为了“有一个终态”擅自从初态加lambda到f，那会至少多收空串。

考试角度：（A 级：HW01-2025T1-题目.pdf Q5；HW02-2025T1-题目-更新.pdf Q1，考的是子集构造与补语言。）见附录 A2。

考试角度：（A 级：期中练习-含解答-学期待核.pdf Q1(1–4)，对应有限自动机判断题；扫描卷题面经视觉读取，练习卷不冒称正式考卷。）见附录 A3。

本讲核心考点

• 机器等价只要求语言相等（p.160–165；C 级）。
• 子集构造取可达集合，最坏有指数数量（p.166–184；C 级）。
• 一般初态取空闭包，终态看非空交集（p.175–182；C 级，须注明简化条件）。
• 正确性需证明既不漏收也不多收（p.185–196；C 级）。
• 单终态NFA转换保留原转移、额外添加结束状态（p.198–201；C 级）。

附录

A1 子集构造的完整双向不变式证明（p.185–196）

定义 $R(u)$ 为原NFA从初态出发、标签为u的所有有限运行能到达的状态，包括前后任意有限次lambda移动。新DFA在u后的状态记 $D(u)$。证明对所有有限串u有 $D(u)=R(u)$。

基础u为空：新初态定义为 $C(\{q_0\})$，这就是所有零个实际输入字符可达的位置，因此两边相等。

假设对u成立，考察ua。任取 $r\in R(ua)$。成功到r的路径中，最后一个实际字符a必从某个p沿a边到t，随后只走lambda到r；a之前的路径标签为u，所以 $p\in R(u)=D(u)$。构造处理D(u)中的所有p，必收录t，并在闭包中收录r，因此 $R(ua)\subseteq D(ua)$。

反过来任取 $r\in D(ua)$。根据新转移的定义，必存在 $p\in D(u)$ 和一条原机a边p→t，再有lambda路径t到r。归纳假设给 $p\in R(u)$，即存在原机从初态读u到p的真实路径。连接这条路径、a边、lambda路径，就得到读ua到r的路径。因此 $D(ua)\subseteq R(ua)$。两个方向一起完成集合相等。

最终，新机接受w当且仅当 $D(w)\cap F\ne\varnothing$；用不变式替换为 $R(w)\cap F\ne\varnothing$，正是原机存在接受运行的定义。空转移循环不妨碍证明：可达性只需要一条有限路径见证，闭包最多收录有限Q中的状态。

回到正文：两个方向都不能省（p.194–196）

A2 作业/往年题演练（非讲义内容）：子集构造与补语言

题面块（HW01-2025T1-题目.pdf（本地课件） · Q5 · p.1）：

p.1 Find a dfa that accepts the complement of the language defined by the following nfa: (20%)

图已目视：初态q0，终态q3、q5；a边q0→q1、q0→q4、q1→q2、q2→q3、q4→q5、q5→q4，无其他边，单字母表{a}。可达子集DFA如下，表中接受列已经取补：

原NFA接受长度2、3以及所有正偶数长度，故补接受λ、a以及至少5的奇数长度，与表一致。每行对a有后继，已经完整；不是直接交换NFA终态。若另给更大字母表，还应加入读其他字符后的空子集接受陷阱。

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

p.1 (20pts) Convert the following NFA into an equivalent DFA on $\Sigma=\{0,1\}$.

原图初态q0、终态q2；边q0—1→q0、q0—0→q1、q1—0→q1、q1—1→q0、q1—1→q2、q2—1→q2。由初集{q0}作可达子集：

例如01：A→B→C接受；010：A→B→C→B拒绝。所有后继已留在三集内，不需要列不可达的全部8个子集。C读1时q0与q2各自仍在原态，所以合并仍为C。

回到正文：子集构造与补语言

A3 作业/往年题演练（非讲义内容）：有限自动机判断题

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

p.1 Mark each statement as True or False. No proof is required. (3 pts each)

p.1 1. If a language L is accepted by some NFA, then there exists a DFA that accepts L.

p.1 2. In a DFA, a single state may have two distinct outgoing transitions both labeled by the same input symbol.

p.1 3. In an NFA, a state may have zero outgoing transitions.

p.1 4. Every finite language is regular.

依次True、False、True、True。1由含λ闭包的子集构造，最终子集含任何NFA终态即接受；2违反每状态/符号唯一后继；3集合值转移可为空；4可对有限多个固定串各建一条接受路径并作有限并，空语言另用无终态机器。第4不能反过来说正则语言必有限，例如a星无限。题面不要求证明，学习附录补这些原因帮助分辨相邻概念。该资料学期待核，作为练习题证据，不称已核实的某届正式期中。

回到正文：有限自动机判断题

来源与证据

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

• 原件：lec2.pdf（本地课件），PDF p.159–201。

• 本次复核：2026-10-13；逐页读取 lec2.pdf 文字，核对主要机器图与图片题例，补全转移表及主线证明。p.53 原图在 PDF 渲染中缺失部分图元，正文已提供明确标为补充的完整构造。