简介：这份课程设计报告面向计算机专业学生与编译原理初学者，聚焦有限自动机中空闭包 ε-closure(I) 的算法落地，帮助读者把课堂上的集合推导转化为可运行的 Java 程序，并配套完整的状态转换图绘制方案。包内共 1 个 docx 文件，约 177KB，按需求分析、概要设计、详细设计、测试与分析、用户使用说明、总结、参考文献与附录源代码的顺序展开，既可直接作为课程设计模板参考，也可用于理解 NFA 求子集与读空的实现细节。报告中给出了数组、图与哈希表的数据结构选型，拆分出前端输入、后台处理、读空、读字母表与状态子集扩展等模块，并说明对初态 X 递归求空闭包、再用静态字符串逐层累积结果的思路；测试部分以两组含 ε 弧的自动机实例演示所有状态子集及其空闭包输出，并讨论状态节点布局的通用性。已有 1287 人学习下载，适合需要对照代码复现算法、撰写报告或备考编译原理的学习者参考。

1. ε-closure 不是“多走几步空弧”，而是子集构造法的唯一动力源

很多人第一次写 ε-closure（I），脑子里想的都是个体力活：把所有 ε 弧走一遍，把能到达的状态塞进集合，收工。真拿 Java 去实现一个能处理任意 NFA 的空闭包程序时才会发现，难的不是“走一遍”，而是走完之后这批集合怎么喂给子集构造法，让 NFA 一步步塌缩成 DFA。编译原理课上那句“ε-closure(I) 是从 I 出发经任意条 ε 弧可达的状态集合”，省掉了一个关键事实：它才是子集构造每一步的动力来源，move 只负责吃一个字母，剩下的“把新状态补全”全靠闭包兜底。少了这一步，NFA 转 DFA 立刻退化成一比一映射，所有分支当场消失。

这份课程设计报告把实现拆成三个函数：读空的、读字母的、把所有状态子集一次性结算闭包的循环。三层正好对应原理到代码的距离，下面从机制往回推，看每一步为什么必须这么写，以及哪些写法会在你自认为跑通的时候悄悄翻车。

2. 空闭包到底在算什么：可达性、虚拟首尾状态与存储选型

2.1 从数学定义到队列：闭包本质是一次带环的可达性搜索

ε-closure(I) 的完整定义是 I ∪ { t | 存在 s ∈ I，使 s 经任意条 ε 弧可达 t }。这里有两个容易被读漏的词：“零条”和“任意条”。零条意味着自反性，I 里每个状态无条件属于自己的闭包；任意条意味着传递性，走一步、走十步、绕着环走一圈再回来，都算。两条合起来，闭包就是一个包含自身的传递闭包，换成人话说：从 I 出发沿 ε 边走，能踩到的所有点。

这个定义天然适合图搜索，不适合纯递归展开。原因很直接：ε 弧可以成环（比如 5 --ε--> 1、1 --ε--> 5 这种），裸递归会沿着环无限展开，直到栈溢出。合格写法是维护一个 visited 集合，让“已收录”这件事同时承担两个职责——去重，以及判断是否需要继续从该点扩散。

// 邻接表：状态 -> (字母 -> 可达状态集合)，ε 也当作一个特殊字母存在里面 Map<String, Map<String, Set<String>>> delta; Set<String> epsilonClosure(Set<String> start) { // 零条 ε 弧：起点自身无条件属于闭包，先全部放进去 Set<String> closure = new HashSet<>(start); Deque<String> stack = new ArrayDeque<>(start); while (!stack.isEmpty()) { String s = stack.pop(); // getOrDefault 两层兜底，避免没有出边的状态触发 NPE Set<String> next = delta.getOrDefault(s, Collections.emptyMap()) .getOrDefault("ε", Collections.emptySet()); for (String t : next) { // add 返回 true 表示首次收录，才需要继续从 t 往外扩 if (closure.add(t)) { stack.push(t); } } } return closure; }

这段代码里最关键的一行是closure.add(t)。它返回布尔值，为 false 说明 t 已经在闭包里，可能是自反性放进来的，也可能是别的路径先到一步。用返回值决定要不要入栈，等于把“去重”和“剪枝”合并成一次操作，不需要额外的 visited 数组。参数上，start 传的是任意状态子集而不是单个状态，因为闭包的定义域本来就是子集，接口按定义域设计，调用方就不用自己拆包。

复杂度上看，每个状态最多入栈一次，每条 ε 弧最多被检查一次，总代价是 O(|Q| + |δε|)，和图的广度优先遍历同一个量级。这一点很重要，因为闭包在子集构造里会被调用几十上百次，任何一次写成 O(|Q|²) 都会在后面成倍放大。

2.2 引入 X 和 Y：虚拟首尾状态解决了哪种边界问题

NFA 允许多个初态、多个终态，这两条自由带来的麻烦是：子集构造需要一个唯一的起点，还需要一个统一的接受判定。工程上最省事的做法是给自动机补两个虚拟状态，X 和 Y，然后从 X 拉一条 ε 弧到每一个原初态，从每一个原终态拉一条 ε 弧到 Y。

补完之后收益立刻显现。第一个状态子集不再是“所有初态的并集再求闭包”，而是干净利落的 ε-closure({X})，一行代码的事。接受判定也不再需要拿子集去和终态集求交集，只看这个子集里有没有 Y：有，就是接受状态；没有，就不是。X 和 Y 本身不消耗任何字母，所以它们不会污染 move 的结果，只参与闭包计算。

报告里有一句很诚实的交代：因为能力有限，X 和 Y 被固定连到一个节点上，并直接写进状态转移函数。这个简化会让自动机的通用性打折——它只对“初态唯一”或“终态唯一”的 NFA 成立，遇到多初态输入会漏掉分支。但它同时揭示了一个真实的设计动机：X、Y 不是算法的一部分，是接口适配层，适配层写死到什么程度，取决于你愿意为通用性付出多少解析复杂度。

2.3 状态、字母表、产生式用什么存：三种结构各管一段

报告里说用了数组、图、哈希表，这个组合不是随手凑的，各自对应一个层次。产生式用String[]存，是因为输入来自文件，一行一条，最省事的序列化方式是原样保留字符串；图用邻接表存，是因为算法要反复问“从状态 s 出发走符号 a 能到谁”，这个问题在邻接表上是 O(1) 查表，在字符串数组上要扫全表；哈希表用HashSet存状态子集，是因为闭包的语义就是集合，去重必须免费。

表格右侧那一列才是真正值得警惕的地方。产生式数组的线性扫描在状态数上到几十以后就开始拖慢整体，而字符串哈希在子集数量上千时会明显不如位图。这两处代价在课程设计的规模下完全看不出来，所以很容易被当成“没问题”的写法带进更大的项目里。

3. 子集构造的主循环：Ia 为什么必须“读空—读字母—再读空”

3.1 move 与闭包的复合：Ia 的推导以及在循环里重复读空的收益

Ia 的定义只有一行：Ia = ε-closure(move(I, a))。拆开看是两段动作，先对子集 I 里每个状态走一条 a 弧，收集所有落点，得到 move(I, a)；再对这堆落点求一次 ε 闭包。为什么第二段闭包不能省？因为 a 弧落点可能还挂着 ε 弧，那些“顺带能到”的状态同样属于下一步的可达集合，漏掉它们就会在后续某个字符上丢分支。

那为什么不需要在 move 之前也读一次空？这涉及子集构造算法必须维持的一个不变量：参与运算的每一个状态子集，本身已经是闭包。初始子集 ε-closure({X}) 天然满足，后续每个 Ia 按定义也满足，归纳下来所有子集都闭合。既然 I 已经闭合，再对它求一次闭包就是恒等操作——闭包是幂等的，ε-closure(ε-closure(I)) 等于 ε-closure(I)。

这一点直接解释了报告里那个“读空—读 a—读空”的写法为什么逻辑上成立但没有必要：前一次读空是防御性的，它保证即便调用方递进来一个裸子集（用户手动指定某个状态子集求 Ia 的情况），结果依然正确；代价是每个子集每个字母都多一次遍历。这类多余操作在课程设计里无所谓，在正经构造器里会被去掉。看清这个取舍，比死记住三步顺序有用得多。

3.2 未标记子集表：worklist 怎么保证一定收敛

子集构造最经典的写法是维护两张表：一张存已经处理过的子集，一张存发现了但还没展开的子集。每次从后者取出一个，标记，然后对字母表里每个字符算 Ia，新子集如果没出现过就塞回后者。这个过程一定终止，因为子集只能取自 Q 的幂集，幂集有限。

Set<Set<String>> allSubsets = new LinkedHashSet<>(); // 已发现子集，Linked 保序 Deque<Set<String>> worklist = new ArrayDeque<>(); // 待展开子集 Set<String> init = epsilonClosure(Set.of("X")); // 第一个子集：X 的闭包 allSubsets.add(init); worklist.push(init); Set<String> alphabet = Set.of("a", "b"); // 字母表，不含 ε while (!worklist.isEmpty()) { Set<String> I = worklist.pop(); for (String a : alphabet) { Set<String> moved = new HashSet<>(); for (String s : I) { // move(I, a)：只走一条 a 弧 moved.addAll(delta.getOrDefault(s, Collections.emptyMap()) .getOrDefault(a, Collections.emptySet())); } if (moved.isEmpty()) continue; // 空子集不构造，也没有闭包 Set<String> next = epsilonClosure(moved); // 落点再求闭包 if (allSubsets.add(next)) { // add 返回 true 说明是新子集 worklist.push(next); } } }

这里allSubsets.add(next)的返回值同样被当成判重信号用，和闭包里的closure.add(t)是同一个套路：集合的 add 天然告诉你“这个元素以前在不在”。moved.isEmpty()那一行是必须的，因为空集求闭包仍是空集，把空集塞进集合会让后续遍历多出一堆无意义的空壳，还会在打印结果时冒出一行[]，报告里那个“空代表状态子集为空的情况”，根子就在这里。

LinkedHashSet而不是HashSet，是为了让子集的发现顺序稳定。这个细节在调试阶段价值极大：哈希顺序每次运行都可能不同，两组结果按行比对时你会以为算法错了，其实是打印顺序变了。

3.3 状态爆炸的上界与工程上该在哪里踩刹车

理论上，n 个状态的 NFA 最多能长出 2^n 个 DFA 状态，这个上界不是吓唬人的，像(a|b)*a(a|b)^k这类结构就能逼近它。课程设计里状态数通常个位数，随便怎么写都能跑；一旦换到词法分析器真实规模（关键字、标识符、注释、字符串十几条规则拼起来的 NFA），子集数量很容易上到几百。

所以实现层面有三处值得提前留好接口：状态子集用BitSet而不是HashSet<String>，哈希开销直接降一个量级；子集判重可以先算哈希再比对，避免集合之间反复逐元素比较；构造过程做成惰性的，别一上来就把所有子集全展开再打印，只查某个子集的闭包时没必要把整张表建完。报告里那段mapmax循环就是典型的“全量结算”，先有全部子集，再逐个求闭包，规模小时它是最好读的写法，规模大时它是第一个该改的地方。

4. 源码拆解：三个核心函数真实的边界在哪里

4.1 RestltList 的递归为什么“只吃到一层”

报告里对新初态 X 读空的函数是这样写的：

public static String RestltList(String string, String[] strings) { for (int i = 0; i < strings.length; i++) { // 只拿当前结果串的最后一个字符去匹配产生式左部 if (String.valueOf(string.charAt(string.length() - 1)) .equals(String.valueOf(strings[i].charAt(1)))) { if ("ε".equals(String.valueOf(strings[i].charAt(3)))) { string += String.valueOf(strings[i].charAt(6)); RestltList(string, strings); // 递归调用的返回值没有被接住 } } } return string; }

两个问题叠在一起。第一，函数只盯着结果串的最后一个字符做延展，也就是说一次调用只顺着“末尾状态”的一条出边走，如果闭包需要从中间某个状态分叉，它看不到。第二，递归那一行的返回值被直接丢弃，而 Java 参数是值传递，string +=只修改当前栈帧里的局部变量，递归里追加的字符根本回不到外层。

有意思的是，这两个 bug 互相抵消了一部分：因为返回值丢了，递归第二层不再往 string 里加东西，所以即便 ε 弧成环，结果串也不会无限增长。它“碰巧”不会栈溢出，但代价是闭包只吃到一层，多级 ε 链（X→1→2→3）会算漏。报告正文里说“定义了一个静态变量字符串来接收它”，可代码里用的是参数传递，说明当时试过静态变量但最终版本没落实。这类“注释和代码对不上”的地方，是读别人的课程设计代码时最该盯紧的位置。

4.2 RestltListA 的接口错配：传进来的是子集还是单个状态

public static String RestltListA(String string, String s, String[] strings) { String resultA = ""; for (int i = 0; i < strings.length; i++) { // 这里拿整个 string 去和一个字符比较 if (string.equals(String.valueOf(strings[i].charAt(1)))) { if (s.equals(String.valueOf(strings[i].charAt(3)))) { resultA += String.valueOf(strings[i].charAt(6)); } } } return resultA; }

string.equals(charAt(1))这一行是死路。如果调用方按名字传进来一个子集串"123"，它永远不可能等于任何单个字符，函数恒返回空串。也就是说这个函数实际只能接受单个状态，它是 move 的单步版本，不是子集版本。

这恰好点出一个接口设计原则：move 的最小职责是“一个状态、一个字母、一条出边”，子集的循环应该放在调用方。报告的设计说明里写的是“对传入的状态子集进行循环，然后再嵌套循环产生式”，贴出来的代码里并没有那层外层循环，说明贴的是简化版或早期版。函数边界按最小职责切，是让逻辑变简单的关键——切对了，每个函数只看一件事；切错了，就得在函数内部判断“你传给我的到底是一个状态还是一串状态”，判断逻辑本身又会成为新的 bug 来源。

4.3 DuKong 的动态 length 与 mapmax 的哈希顺序

public static String DuKong(String result, String[] strings) { for (int i = 0; i < result.length(); i++) { // 每次循环重新求长度 for (int j = 0; j < strings.length; j++) { if (String.valueOf(result.charAt(i)) .equals(String.valueOf(strings[j].charAt(1)))) { if ("ε".equals(String.valueOf(strings[j].charAt(3)))) { result += String.valueOf(strings[j].charAt(6)); // 边遍历边扩容 RestltList(result, strings); // 返回值再次丢弃 } } } } return result; }

i < result.length()在循环体内部因为result +=而不断变大，新追加的字符会被同一个循环继续访问到，形成一种“边遍历边扩散”的效果。这确实能把多级 ε 链吃干净，但它依赖两个隐式前提：String 不可变，所以+=每次都生成新对象；长度每次重新求，所以循环上界会跟着长。只要有人手贱把它优化成int len = result.length()缓存起来，功能立刻退化。

这种写法本质上是把“队列扩散”伪装成了“循环边界动态变化”，可读性和可维护性都很差。正规写法是两个集合轮换：frontier 放当前待处理状态，next 放本轮新发现的状态，处理完交换引用。这个结构一眼就能看出扩展了几层，也方便加日志。

同一段配套代码里还有HashMap<Set<String>, Set<String>> mapmax，遍历时输出顺序不稳定。调试期拿它和标准答案对行，会得到“结果一样但顺序全乱”的假象。换成LinkedHashMap或者输出前按子集字符串排序，问题立刻消失。

4.4 重写一版：闭包、move、子集构造三段式

把上面这些东西拼起来，一个职责清晰的版本长这样：

// 产生式解析成结构，不再靠 charAt 定位 record Edge(String from, String symbol, String to) {} // ① 闭包：带 visited 的迭代扩散，天然防环 Set<String> closure(Set<String> start, List<Edge> edges) { Set<String> result = new HashSet<>(start); Deque<String> stack = new ArrayDeque<>(start); while (!stack.isEmpty()) { String s = stack.pop(); for (Edge e : edges) { if (e.from().equals(s) && "ε".equals(e.symbol()) && result.add(e.to())) { stack.push(e.to()); } } } return result; } // ② move：只走一条指定字母的弧，不含闭包 Set<String> move(Set<String> I, String a, List<Edge> edges) { Set<String> result = new HashSet<>(); for (Edge e : edges) { if (I.contains(e.from()) && a.equals(e.symbol())) { result.add(e.to()); } } return result; } // ③ Ia：两段复合，顺序不能反 Set<String> ia(Set<String> I, String a, List<Edge> edges) { return closure(move(I, a, edges), edges); }

三段的职责边界很清楚：closure 只认 ε，move 只认指定字母，ia 负责复合。这样写还有个额外好处——求“给定状态子集的空闭包”这个需求变成一次closure(I, edges)调用，不需要先跑完整个子集构造。报告里要求“输出给定状态子集的空闭包”，用这套结构是常数级集成成本；用原来那套“先算全部子集再查表”的做法，用户只想知道一个子集，程序却把整张表算完，属于典型的过度计算。

5. 避坑与排查：字符串建模踩出来的五个坑

5.1 递归读空只多了一层

现象：输入(X,ε)→1 (1,ε)→2 (2,ε)→3，期望闭包{X,1,2,3}，实际输出{X,1}，或者只多一个状态。 原因：递归调用RestltList(string, strings)的返回值没有被接住，Java 值传递下string +=只改当前栈帧的局部变量，深层追加结果全部丢失。 解决：要么改成传一个Set<String>或StringBuilder这类可变容器进去，让每一层都往里写；要么让每层返回自己这一层的并集，由调用方合并。静态变量也能凑合，但并发和多次调用之间必须手动清空，是个更隐蔽的雷。

5.2 状态名一旦超过一位，整个解析全错位

现象：状态名从1,2,3换成q1,q2,q10之后，程序要么报StringIndexOutOfBoundsException，要么算出一堆不存在的状态。 原因：解析靠固定下标，charAt(1)取左部状态、charAt(3)取符号、charAt(6)取右部状态，这套下标只对(1,a)→3这种单字符格式成立。右部一旦是两位数，第七个字符只取到了第一位。 解决：先把产生式按→和,拆开，解析成(from, symbol, to)三元组，再进算法。解析和算法分离是硬要求，别让下标假设渗进计算逻辑。

5.3 换个循环写法结果就变

现象：把for (int i = 0; i < result.length(); i++)改成先缓存长度，原本能算出的多级闭包突然只算出一级。 原因：原写法依赖“循环过程中字符串动态变长、上界每次重算”这个副作用来实现分层扩散，本质是把队列逻辑藏在了循环边界里。 解决：显式用 frontier 和 next 两个集合，或者用队列。把“这一步处理谁、下一步处理谁”写明白，别让结果依赖于循环条件的求值时机。

5.4 同一份输入，两次运行打印顺序不同

现象：结果集合内容完全一致，但每次运行的输出行顺序都不一样，人工对答案时误判成算错。 原因：HashMap、HashSet的迭代顺序由哈希值决定，不做任何保证；子集作为 key 存进去以后，遍历顺序自然漂移。 解决：用LinkedHashMap、LinkedHashSet保留插入顺序，或者在输出前把子集转成排好序的字符串再打印。调试期稳定顺序能省下大量误判时间。

5.5 ε 环把程序拖死

现象：自动机里存在1 --ε--> 2、2 --ε--> 1这样的环，程序要么卡住不动，要么内存一路涨到崩。 原因：闭包扩展时没有 visited 集合，沿环无限展开。用字符串拼接实现的版本更糟，串会无限变长，直到 OOM。 解决：闭包一律用集合承接结果，靠add的返回值判断是否首次访问。凡是“沿边走”的逻辑，先问一句“环上会不会重复进来”，答案是不会，才可以省掉 visited。

6. 设计取舍：字符串建模、固定 X/Y 与全量计算的代价

回头看我经手过的这类实现，最值得记住的不是算法本身，而是三处当时觉得无所谓、后来必须还债的取舍。

第一处是拿字符串当数据结构。产生式用String[]存、状态子集用String拼、闭包结果还是String，好处是写起来快、打印出来直接能看，坏处是所有语义都退化成了字符位置。charAt(6)这类代码在状态名单字符时完全正确，一旦规模上去就全线崩。这不是水平问题，是建模层级选低了：算法层需要的是“状态、符号、转移”三个概念，而字符串只提供“字符”一个概念，中间那层映射得靠人脑维护，人脑一松懈就出错。

第二处是 X、Y 固定连到一个节点。这个简化让“补虚拟首尾状态”从一次遍历退化成两行硬编码，代价是自动机丧失了多初态、多终态的通用性。报告里那句“因为能力有限”很坦诚，但它也提示了一个更普遍的现象：接口适配层的偷懒，往往被误认为算法层的简化。真正的做法是读入时就把 X 连到全部初态、全部终态连到 Y，这一步多写十行，后面所有算法都不用再关心“初态到底有几个”。

第三处是“先算全量再查表”。把全部状态子集求出来、再逐个求闭包、存进 map 打印，逻辑上是闭合的，读起来也顺。但它把两个需求的成本绑在了一起：用户只查一个子集的闭包，程序却付了全量构造的代价。这种绑定在课程设计里看不出来，在真实工具里就是响应时间的分水岭。惰性构造、按需展开，是同一个算法在不同规模下的两种正确形态。

从那以后我每次写闭包类算法，都强制先问三个问题：结果用什么容器装、环上怎么保证不重复进、这个函数的最小输入到底是一个元素还是一个集合。三个问题回答清楚，代码基本一次就能跑对；回答不清楚，就会出现“算出来了但只对了一半”这种最难查的状态。希望这些踩坑记录能帮你少走一遍我走过的弯路，把精力留给真正值得琢磨的子集构造和状态爆炸上。

本文还有配套的精品资源，点击获取