NFA空闭包与子集构造的Java实现及状态转换图绘制

简介：这份课程设计报告围绕编译原理中有限自动机的空闭包 ε-closure(I) 展开，面向正在学习自动机理论、需要完成课程设计，或希望用 Java 实现 NFA 相关算法的高校学生。报告依次包含需求分析、概要设计、详细设计、测试与分析、用户使用说明和总结，重点说明如何读入任意 NFA、保存状态转移信息，计算全部状态子集及指定状态子集 I 的空闭包，并借助状态转换图呈现自动机结构，同时讨论结点布局与通用性。压缩包仅含 1 个 docx 文件，大小约 177KB，正文包含目录、核心函数设计、测试用例与附录源代码，结构完整，适合作为课程设计撰写模板和算法实现参考。已有 1287 人学习，读者可从中获取 NFA 数据组织、递归求空闭包、状态子集扩展以及读空/读字母表函数划分等思路，也能参考测试样例和报告章节安排，用于复现实验、整理设计文档或对照排错。

1. 一个只求空闭包的课设，为什么值得按完整方案来做

编译原理课设清单里，ε-closure(I) 常被当成最轻的那一项：不就是顺着空弧递归走一遍吗。真正开始写代码才发现，麻烦根本不在递归——状态子集没有现成容器，闭包输出没有统一格式，状态转换图更是从零开始画，一个原本以为三小时能收尾的活，能拖成三天。这份用 Java 实现的课程设计报告，把“输入任意 NFA、输出所有状态子集的空闭包、输出指定子集的空闭包、画出状态转换图”四件事拆成需求、设计、实现、验收四段，适合正在交编译原理课设的同学照着搭结构，也适合要做一个自动机小工具的从业者直接改。下面按我实际落地的顺序讲，从需求契约一路讲到答辩时怎么把算法讲明白。

2. 需求拆解：四条硬要求拆成可执行的输入输出契约

题目给的四条基本要求读起来很短，但每一条往下拆都会牵出一串设计决定。写代码之前先把这四条翻译成“程序吃什么、吐什么、出错怎么办”，后面 80% 的返工都能省掉。

2.1 自动机怎么进来：产生式文本格式的约定

第一条要求是“输入 NFA，保存到文件”。学院派的做法通常是把状态集、字母表、初态、终态、转移函数分四到五段写在文本里，程序启动时整体读进内存；而这份课设因为重心在算法，做了一个更轻的取舍——直接把转移函数以产生式字符串数组的形式给出，形如(5,a)→5、(5,ε)→1，状态集和字母表单独一行列出。这种格式的好处是肉眼可读、手工可改、测试数据随手就能编三组，缺点是解析器很脆，这一点在后面避坑章里专门说。

一个能用的输入文件长这样：

STATES:X,1,2,3,4,5,6,Y ALPHA:a,b TRANS:(X,ε)→5 TRANS:(5,a)→5 TRANS:(5,b)→5 TRANS:(5,ε)→1 TRANS:(1,a)→3 TRANS:(1,b)→4 TRANS:(3,a)→2 TRANS:(4,b)→2 TRANS:(2,ε)→6 TRANS:(6,a)→6 TRANS:(6,b)→6 TRANS:(6,ε)→Y

读文件这部分我一般会做三件事：一是按行过滤空行和以#开头的注释行，避免手写测试数据时被自己的注释坑到；二是把STATE、ALPHA、TRANS三类行分别装进三个集合，转移函数保持字符串原样，不做结构化；三是读完之后立刻校验每个产生式的左部状态和右部状态都在STATES里，不在就抛出一条能看懂的错误，而不是等到递归里数组越界。

提示：产生式里空弧符号统一用ε，不要一会儿用ε一会儿用e一会儿用$。这个统一看着是小事，实际是整份代码里最容易埋雷的地方。

为什么不在这一步就把产生式解析成对象？因为这个程序的算法核心是“按状态扫产生式”，扫描时只需要知道左部状态、弧上符号、右部状态三个字段，用对象反而多一层解引用。当然，用固定下标charAt(1)、charAt(3)、charAt(6)去取字段是有代价的，代价就是格式一旦变化，整个程序静默出错——这个取舍我在第 5 章会给出更稳的折中写法。

2.2 三类输出：全子集闭包、指定子集闭包、状态转换图

第二条和第三条要求分别是“输出所有状态子集的空闭包”和“输出给定状态子集的空闭包”。这两条看着只差一个“所有”，实现路径完全不同：前者要先做子集构造，把所有能到达的状态子集枚举出来，再对每个子集求闭包；后者只要拿到用户输入的状态串，直接调一次闭包函数就行。

我的做法是把它们做成同一个底层函数的两个入口。底层是epsilonClosure(start, rules)，输入一个状态串，输出它的闭包串。全部子集闭包那条路，先跑子集构造主循环把所有子集收进一个Map<Set<String>, Set<String>>，再遍历这个 Map，对每个 key 求一次闭包放进 value。指定子集那条路，直接把用户输入的状态串喂给同一个函数。

输出格式上我建议固定成两列对齐：

状态子集====状态子集空闭包 [1, 5]===[1, 5, X, 6, Y] [2, 3]===[2, 3, 6, Y]

用Set而不是String存子集，好处是输出时自动去重、顺序无关，两个子集比较是否相等时不用自己写比较逻辑；坏处是HashSet打印出来的顺序不稳定，如果要给老师演示，建议换成TreeSet或者输出前排序，不然同一份数据跑两次结果顺序不一样，看起来像有 bug。

第四条要求“以状态转换图方式输出，节点大小位置布局合理，具有通用性”，这条是所有要求里最容易被低估的。它不是“画个图就行”，而是要求这套布局对任意输入的 NFA 都成立——状态数从 3 个到 20 个都能看，不能靠手写坐标。这一点放到第 4 章最后一节展开。

2.3 边界情况：空集、孤立状态、多终态

课程设计的评分点往往不在正常路径，而在边界。我在设计阶段列了四类必须处理的输入：

空集这条尤其要注意。原文的测试例二里就有“空代表状态子集为空的情况”，说明作者已经踩过这个点：当一个状态子集经过某个字母后没有可达状态，move 返回空串，这时候如果直接拿空串去求闭包，闭包函数会把空串当成一个合法状态继续往下扫，扫不出东西但也不会报错，看起来“能跑”，实际上主循环可能因此多转一圈。稳妥的写法是在调用闭包之前先判断if (moved.isEmpty()) continue;，空集直接跳过，不进入待处理队列。

孤立状态这条容易被忽略。一个状态如果没有任何入弧，它不会从 X 出发被构造出来，但它可能出现在用户手动输入的指定子集里。所以“指定子集求闭包”这条路径不能复用子集构造的结果，必须能对一个完全陌生的状态串独立求闭包。

3. 总体设计：六模块划分与三张数据表

需求定完之后，接下来的问题是怎么把这一坨逻辑切开。切开的方式直接决定了写的时候顺不顺、改的时候痛不痛。

3.1 数据结构选型：数组、图、哈希表各管一段

这份课设用到的数据结构不多，但每一个都有明确的分工，混用就会出现“明明能跑但结果不对”的玄学问题。

这里要说清楚一个设计上的取舍：产生式为什么用字符串数组而不是Map<状态, List<边>>。原因是这个程序里“扫描”远多于“查找”——求闭包要对每个状态扫一遍全部产生式，求 move 也要对子集里每个状态扫一遍全部产生式。既然无论如何都要全扫，建索引反而增加了构建成本，还会让代码多一层嵌套。当然代价是时间复杂度是 O(状态数 × 产生式数)，状态数上到几十、产生式上到几百的时候会明显变慢，但对课设规模完全够用。

HashMap<Set<String>, Set<String>>这个结构是整个程序的中枢，它同时承担了两件事：一是作为子集构造的“已访问表”，key 存在就说明这个子集处理过了，不再入队；二是作为最终输出的数据源，遍历它就能打印出“子集 → 闭包”的对照表。一份数据两用，省掉了一次重算，也避免了两个容器不同步的经典 bug。

3.2 六个模块与三层调用链

按职责切，这份程序可以分成六块：前端数据传入、后台数据处理与分析、新初态 X 的读空、状态子集读空、状态子集读字母表、子集扩展循环。前两块是 IO 和调度，后四块是算法本体。

调用关系是三层：

主程序 ├─ 读文件 / 收输入 ──→ 产生式数组、状态集、字母表 ├─ 子集扩展循环（第三层调度） │ ├─ move(I, a) ← 读字母表函数 │ └─ epsilonClosure(...) ← 读空函数（被调用两次：前一次作用于 I，后一次作用于 move 结果） └─ 输出层 ├─ 遍历 Map 打印全部子集闭包 ├─ 对用户输入的子集调一次读空函数 └─ 按产生式渲染状态转换图

这个结构最关键的一点是：读字母表和读空是两个严格分离的原子操作，谁都不去调对方。求ε-closure(move(I, a))这件事由上层的调度去拼。原文在总结里写得很直白——“最后在网上找到求状态子集的算法，没想到可以先写两个函数，分别是读字母表和读空的函数，而求状态子集的时候就可以直接按照读空读 a 再读空这个逻辑来写了”。这个拆分是整份课设最值钱的设计决定，比任何一行代码都重要。

为什么要坚持分离？因为如果让 move 函数内部自己去考虑空弧，它就得处理三种情况：先空后 a、先 a 后空、a 前后都空。这三种情况写在一个函数里，分支会迅速膨胀，而且每加一种就动一次核心逻辑，改到最后自己都不敢动。分离之后，move 只管“字母弧一步到位”，闭包只管“空弧任意步”，组合的正确性由调度层保证——这是典型的用结构换复杂度。

3.3 加 X、加 Y：把“任意初态集”变成“唯一初态”

子集构造的起点必须是唯一的。但 NFA 允许有多个初态，怎么办？标准做法是引入一个新的初态 X，从 X 引一条 ε 弧到每个原初态；对称地引入新终态 Y，从每个原终态引一条 ε 弧到 Y。这样“初态集”就变成了“初态 X”，后面的算法可以无脑从 X 开始。

这一步在纸上是两行，在代码里是个坑。原文作者的处理很诚实：“因为我们能力有限，实在想不出如何处理 X 到任意状态节点以及任意状态节点到 Y 的情况，所以写的时候我们就让 X 和 Y 都固定连接到那一个节点，并将其作为状态转移函数写到自动机的状态转移函数里。”

也就是说，他们的做法不是真的遍历初态集去连弧，而是手工在输入的产生式里写死一条(X,ε)→5和一条(6,ε)→Y。这个简化在单初态、单终态的 NFA 上完全成立，而且省掉了“动态生成转移函数”的一整块代码；但对多初态的输入就不成立了。

我在自己复现时保留了他们的简化，但加了一层保险：读文件的时候扫描一遍产生式，统计所有形如(X,ε)→?的规则条数，如果发现初态集里有状态从来没被 X 连到，就在控制台打一条警告——“状态 3 没有任何入弧，可能不会出现在子集构造中”。这样既不改变算法，又让简化带来的局限变成可见的，答辩时被问起来也有话说。

注意：加 X 加 Y 之后，最终输出的状态子集里会混进 X 和 Y。如果报告里要给出去 ε 之后的“纯净”自动机，记得在输出前把这两个符号过滤掉，否则老师第一眼就会问“X 是哪来的”。

4. 核心算法实现：读空、读字母表与子集扩展的三段式

算法本体只有三个函数加一个循环，但每个都有细节。这一章按“先看代码、再看为什么这么写”的顺序讲，代码都是可以直接编译跑的 Java。

4.1 读空函数：递归展开与静态累加器

求一个状态的 ε 闭包，逻辑是：先把状态自己放进去，然后反复找它出发的 ε 弧，把到达的状态也放进去，新放进去的状态继续展开，直到没有新状态为止。

麻烦在于返回值。一个状态展开之后可能带出 5 个新状态，但 Java 的方法一次只能返回一个值。原文作者试了很多办法，最后用的是静态变量：

private static StringBuilder closureBuf; // 静态累加器：一次调用只能返回一个串，累加靠它 /** * 求一个状态（或状态串）的 ε-闭包 * @param start 起点，通常是新初态 "X" 或某个状态子集的串表示，如 "15" * @param rules 产生式数组，元素形如 "(5,ε)→1" * @return 闭包内所有状态拼成的串，如 "X516Y" */ public static String epsilonClosure(String start, String[] rules) { closureBuf = new StringBuilder(start); // 闭包首先包含自身 expand(rules); String result = closureBuf.toString(); closureBuf = null; // 用完即清，防止污染下一次调用 return result; } private static void expand(String[] rules) { for (String rule : rules) { // rule 形如 "(5,ε)→1"：第 1 位是左部状态，第 3 位是弧上符号，第 6 位是右部状态 if (!"ε".equals(String.valueOf(rule.charAt(3)))) continue; String from = String.valueOf(rule.charAt(1)); String to = String.valueOf(rule.charAt(6)); // 只有当 from 已在闭包里、且 to 还不在闭包里时才展开，避免死循环 if (closureBuf.indexOf(from) >= 0 && closureBuf.indexOf(to) < 0) { closureBuf.append(to); expand(rules); // 以新状态为起点继续展开 } } }

这段代码有三个参数级的细节需要说明。第一，closureBuf是静态的，意味着这个函数不可重入、不线程安全——对课设完全够用，但如果要在别处并发调用，必须改成传引用的写法。第二，每次调用结束必须把它置空，否则下一次调用会拿到上一次的残留，这是静态变量最经典的翻车方式。第三，递归的终止条件写成了“to 还不在闭包里”，而不是“扫完所有规则”，因为只要闭包还在增长就还有规则没被充分利用，必须重扫。

原文里那个版本用的是string += ...然后把string作为参数递归传下去。这个写法在 Java 里是无效的——字符串是不可变对象，+=产生的是新对象，递归返回之后外层的string还是旧值，所以拿到的结果往往是“只展开了一步”。这也是为什么原文强调“每次递归调用都需要累加而不能清空，所以我是定义了一个静态变量字符串来接收它”。真正的累加语义必须由可变容器承担，用StringBuilder是最直接的修法。

递归深度要不要担心？理论上一个 n 个状态的自动机，空弧链最长 n 条，递归深度不超过 n，对课设规模毫无压力。但如果输入的 NFA 状态数上千，递归写法会栈溢出，那时候要把expand改成 BFS：用一个Queue<String>存待展开的状态，出队一个扫一遍规则，新状态入队且入闭包。逻辑完全一样，只是换了个遍历顺序，我一般会在报告里把这个改进方案写上一段，答辩时是个加分项。

4.2 读字母表函数：只做 move，不掺 ε

第二个函数是 move，输入状态子集和一个字母，输出“从子集里任一状态走一条标号为该字母的弧能到达的所有状态”。它不碰 ε，一条空弧都不看。

/** * 单字符 move：只走标号为 a 的弧，绝不读 ε * @param stateSet 当前状态子集，串表示，如 "15" * @param a 字母表中的一个符号，如 "a" * @param rules 产生式数组 * @return move 结果串，去重后拼接；返回空串表示结果为空集 */ public static String move(String stateSet, String a, String[] rules) { StringBuilder result = new StringBuilder(); for (int i = 0; i < stateSet.length(); i++) { // 子集里逐个状态扫 String s = String.valueOf(stateSet.charAt(i)); for (String rule : rules) { if (s.equals(String.valueOf(rule.charAt(1))) && a.equals(String.valueOf(rule.charAt(3)))) { String to = String.valueOf(rule.charAt(6)); if (result.indexOf(to) < 0) result.append(to); // 手动去重 } } } return result.toString(); }

参数stateSet是串而不是 Set，是为了和读空函数的接口保持一致——读空函数的返回也是串，这样两个函数可以直接串起来调用，中间不需要一次“串转集合再转回串”的冗余转换。代价是去重要手动做，result.indexOf(to) < 0这一句不能省，否则会出现"112"这样的重复状态，拖到后面闭包计算时虽然Set会再去一次重，但中间过程的字符串长度会膨胀。

还有一个容易被忽略的点：move 的结果可能是空串。空串在字符串语义下是个合法值，但它在状态集语义下代表“空集”。这两个语义不能混。如果调用方把空串当成“一个叫空的合法状态”继续传给闭包函数，闭包函数会尝试在产生式里找左部为空的规则，什么也找不到，返回空串，看起来“能跑通”，但这只是因为错误被静默吞掉了。正确的处理是在调用方判断：

String moved = move(current, a, rules); if (moved.isEmpty()) continue; // 空集不入队，也不求闭包

这一行是整个程序里最容易漏、漏了又最难查的一行。第 5 章会再提一次。

4.3 子集扩展主循环：读空—读 a—再读空

三个函数里最难写的是第三个——对状态子集求闭包。它和 4.1 那个闭包函数同名不同义：4.1 处理的是单个状态，这里处理的是“move 之后得到的一串状态”，而且这一串状态里每一个都要再展开一次闭包。

原文的写法是DuKong(result, strings)：遍历串里每个字符，扫产生式找空弧，找到就把右部追加到result上，再递归调一次RestltList。

/** * 对 move 的结果整体求闭包：串里每个状态各自读空，结果合并去重 * @param result move 返回的状态串 * @param rules 产生式数组 */ public static String closureOfSet(String result, String[] rules) { StringBuilder merged = new StringBuilder(result); for (int i = 0; i < merged.length(); i++) { String single = String.valueOf(merged.charAt(i)); String sub = epsilonClosure(single, rules); // 复用单状态的闭包函数 for (int j = 0; j < sub.length(); j++) { String ch = String.valueOf(sub.charAt(j)); if (merged.indexOf(ch) < 0) merged.append(ch); // 合并去重 } } return merged.toString(); }

注意这里复用了 4.1 的epsilonClosure，而不是复制一份逻辑。原文当时是写了两份读空函数，一份给 X 用、一份给子集用，两份逻辑高度相似。合并成一份的好处是：将来闭包算法要改（比如改成 BFS），只改一处；坏处是每次调用都要重新初始化静态累加器，有一点开销——但这个开销在课设规模下可以忽略。

有了这三个函数，子集构造的主循环就是纯粹的调度：

Map<String, String> subsetMap = new HashMap<>(); // 子集 → 子集闭包 Queue<String> queue = new LinkedList<>(); String first = epsilonClosure("X", rules); // 第一个子集就是 X 的闭包 subsetMap.put(first, first); queue.offer(first); while (!queue.isEmpty()) { String current = queue.poll(); for (String a : alphabet) { String moved = move(current, a, rules); // ① 读 a if (moved.isEmpty()) continue; // 空集跳过 String next = closureOfSet(moved, rules); // ② 再读空 if (!subsetMap.containsKey(next)) { // ③ 只收新子集 subsetMap.put(next, next); queue.offer(next); } } }

这个循环里有三处需要说清楚。第一处是起始值：epsilonClosure("X", rules)直接就是第一个状态子集，不需要先 move 再闭包，因为 X 只有空弧、不可能经过字母。这正是原文说“因为 X 是新加的肯定不会经过字母表的字母，所以 X 的空闭包即为该 NFA 的第一个状态子集”的意思。第二处是收敛条件：subsetMap.containsKey(next)是唯一的去重依据，所以 key 的比较必须可靠——用字符串做 key 时，"15"和"51"是两个不同的 key，会导致同一个子集被重复处理、队列永远清不空。修法是每次插入前把串排序，或者干脆用TreeSet<String>做 key（TreeSet的equals是按内容比较的）。第三处是外层两层循环的顺序：先 poll 一个子集，再遍历全部字母，这个顺序保证了每个子集都会被完整处理一次，不会出现“处理到一半又插进新子集”的混乱。

原文最后那段求全部子集闭包的代码，本质上就是遍历subsetMap的 key，对每个 key 调一次闭包，再塞进一个Map<Set<String>, Set<String>>里输出。它和上面这段主循环是两件事：主循环负责“把子集找全”，遍历输出负责“把每个子集的闭包算出来”。有些实现会把这两件事合并——在构造子集的同时顺便算闭包——这样确实省一次遍历，但会让主循环的职责变重，调试时不好定位问题出在哪一步。我倾向于分开写，多一次遍历换一次清晰的排查路径。

4.4 状态转换图的绘制与节点布局

第四条要求“以状态转换图方式输出，要求状态结点大小位置布局合理，具有通用性”，这条没有现成算法可抄，得自己设计。

我的做法分三步。第一步是从产生式生成边表：扫一遍规则，把每条规则解析成(起点, 标签, 终点)三元组，同一起点同一终点的多条规则合并标签（(5,a)→5和(5,b)→5合成一条边标a,b）。第二步是分层：用 BFS 从 X 出发给每个状态标一个层号，X 是第 0 层，X 的直接后继是第 1 层，依此类推。第三步是按层排布坐标：同一层的状态在垂直方向等距排开，层与层之间在水平方向等距。

这套布局对课设里的自动机足够通用，原因是它不依赖任何硬编码坐标，状态数从 3 个到 20 个都能自动撑开。它唯一处理不好的是带自环和带回边的图——自环会在节点上画一个小圈，回边会横穿中间层。我在实现时加了两个补救：自环单独画成节点上方的小圆弧，回边画成从节点下方绕行的曲线，避开中间层的节点。如果状态数超过 15 个，再加一个简单的“层内错位”，让相邻两层的节点水平偏移半个间距，减少连线交叉。

如果不想自己写渲染，也可以只输出一份结构化的图描述（节点列表 + 边列表 + 建议坐标），交给前端用现成的图形库渲染。课设报告里我建议把这两种方案都写进去，说明为什么选了自绘——自绘不引入外部依赖，答辩现场断网也能跑，这个理由在任何评审场合都站得住。

5. 避坑与排查：五个最容易在同一处翻车的点

这一章列的都是我复现这份课设时真实卡住过的地方，按“现象 → 原因 → 解决”写，遇到同类问题可以直接对照。

5.1 递归读空只返回了最后一步的结果

现象：对一个有明显多级空弧链的 NFA 求闭包，输出里只有起点和一两个直接后继，深层的状态全丢了；但换成空弧少的数据又正常，看起来像“有时候对有时候错”的玄学。

原因：用String做累加器，string += to之后把string递归传下去。Java 字符串不可变，+=产生的是新对象并赋给方法内的局部变量，递归调用返回之后，外层的string引用没有变化，所以上层看到的还是展开前的值。递归深度越深，丢失的层数越多。

解决：把累加器换成可变容器。类静态字段StringBuilder是最省事的写法，每次入口处重置、出口处置空；更规范的做法是把StringBuilder作为参数从头传到尾，避免静态状态。改完之后同一组数据立刻正确。

5.2 产生式用固定下标解析，多一个空格就崩

现象：把测试数据从(5,a)→5改成(5, a)→5（逗号后加了个空格），程序不报错，但结果全乱，move 结果为空，子集构造只构造出一个子集。

原因：解析靠的是charAt(1)、charAt(3)、charAt(6)这三个固定下标。格式一变，下标指向的字符就全错位了——charAt(3)本来该是弧上符号，加了空格之后变成了空格字符，"ε".equals(...)永远为假，空弧一条都读不到。

解决：在保留字符串存储的前提下，把这几个下标提取成常量并加校验：

private static final int IDX_FROM = 1; // "(5,ε)→1" 中左部状态的位置 private static final int IDX_LABEL = 3; // 弧上符号的位置 private static final int IDX_TO = 6; // 右部状态的位置 private static void checkRule(String rule) { if (rule.length() <= IDX_TO) { throw new IllegalArgumentException("产生式格式不正确：" + rule); } }

更好的做法是读文件时先做一次规范化：去掉所有空白字符、把全角括号统一成半角，再存进数组。这样下标解析虽然还是脆，但至少脆在一个受控的输入上。报告里我会把这条写成“格式契约”，说明程序对输入格式有明确要求，而不是默默出错。

5.3 move 之后忘了再闭包，子集少一半状态

现象：子集构造跑出来的子集数量明显偏少，少了那些“经过一个字母之后还能走空弧到达”的状态，最终 DFA 的状态数对不上。

原因：只写了next = move(current, a)，漏掉了外面的closureOfSet。这一步漏掉之后，得到的不是ε-closure(move(I,a))，而是裸的move(I,a)，所有通过空弧间接到达的状态全被丢掉。

解决：把“读空—读 a—再读空”写成一个不可拆的私有方法，主循环只调它：

/** ε-closure(move(I, a))，封装成一步，防止漏掉外层闭包 */ private static String nextSubset(String current, String a, String[] rules) { String moved = move(current, a, rules); if (moved.isEmpty()) return ""; return closureOfSet(moved, rules); // 外层闭包不能省 }

封装成一步之后，调用方就没有“忘记”的机会了。这条经验在任何多步组合的算法里都成立：只要某两步必须成对出现，就用一个函数把它们锁死。

5.4 子集去重不彻底，主循环收敛不了

现象：程序跑一段时间后队列越积越长，控制台疯狂打印子集，半天不结束；偶尔在状态数多的输入上直接卡死。

原因：用字符串做HashMap的 key，"15"和"51"被当成两个不同的子集。同一个子集从不同路径被构造出来时，成员顺序不同，串就不同，containsKey判断失败，于是被重复入队，无限循环。

解决：子集入队前统一排序，或者直接用有序集合做 key：

/** 把状态串规范化成有序串，保证 {1,5} 和 {5,1} 得到同一个 key */ private static String normalize(String states) { char[] arr = states.toCharArray(); java.util.Arrays.sort(arr); return new String(arr); }

主循环里subsetMap.containsKey(normalize(next))、queue.offer(normalize(next))全部走规范化后的串。这一改之后队列立刻收敛，因为不同路径构造出的同一个子集在比较时是相等的。

5.5 状态图节点全挤在一起，图成了黑匣子

现象：状态数超过 8 个之后，输出图里的节点互相重叠，连线上串着好几个节点，看不出谁连谁，被评价为“没有达到布局合理的要求”。

原因：坐标是按固定间距算的，间距没跟状态数挂钩。状态少的时候看着正常，状态一多，同一层的节点超出画布宽度，就全叠在边缘。

解决：把画布尺寸和状态数绑定，层内间距、层间间距都按“可用宽度 ÷ 最大层节点数”动态计算，并给每个节点留一个最小间距下限。另外加一条：如果某一层的节点数超过阈值（比如 6 个），自动拆成两行错位排列。这样状态数从 3 到 20 都能撑住，通用性这条要求才算真满足。

6. 测试验收与答辩：三组数据怎么跑、怎么讲

验收这一环最容易被糊弄过去——程序能跑、结果看着对，就觉得完事了。真到答辩现场，老师随手改一个数据，程序输出错乱，前面的印象全白搭。我一般会准备三组数据，每组专门打一个算法环节，跑完能覆盖住核心逻辑。

跑的时候按固定顺序：先跑用例一，看第一个子集是不是 X 的闭包；再跑用例二，重点看空集那一行有没有正常输出，而不是抛异常或者静默跳过；最后跑用例三，看空弧夹在字母弧中间时，move 之后的状态有没有被外层的闭包补全。三组都过了，再去改状态数，把用例一改成 12 个状态，看子集数量和运行时间，顺便验证 5.4 那个去重改对了没有。

答辩讲算法，我的经验是不要从数据结构讲起，从一张手画的小图讲起。先在纸上画三个状态、一条空弧、一条字母弧，问一句“从状态 1 出发，经过 a 之后能到哪几个状态”，等对方答完，再把答案拆成“先读 a 到谁”和“读 a 到的那个状态还能空走到谁”两半，这时候再说“所以我把 move 和闭包拆成两个函数，主循环按读空—读 a—再读空拼起来”。这个讲法比直接念代码强，因为它让对方先看见问题，再看见解法，顺序对了，说服力就出来了。

还有一个必被问的问题：“为什么要加 X 和 Y？”标准回答是“为了让初态唯一，否则子集构造没有统一起点”，但更值分的回答是补一句“我们这版把 X 的连弧写死在产生式里，只支持单初态单终态，多初态需要动态生成转移函数，这块是已知的简化”。主动交代局限，比被问出来强太多。

从那以后我每次做这类算法课设，都会强制走一遍“三组数据 + 一次边界改参”，哪怕代码看起来再简单。因为算法题的错误从来不在主路径上，全藏在空集、自环、多初态这些边角里，不主动去撞，永远不知道它在那儿。希望帮到你。

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