简介：面向计算机专业学生与编译原理课程设计学习者的一份Java实现课程设计报告，聚焦有限自动机NFA的空闭包ε-closure(I)计算。报告按需求分析、概要设计、详细设计、测试与分析、用户使用说明与总结展开，围绕读入NFA、保存转换关系、输出全部状态子集及指定状态子集的空闭包进行说明，并交代引入初态X与终态Y、递归读空、对状态子集读字母表、逐步扩展状态子集直至不再产生新集合等关键模块，最终以状态转换图呈现自动机结构，并讨论状态结点大小与位置布局的通用性要求、测试数据与结果分析。压缩包仅含1个docx文件，大小约177KB，附录附有Java程序源代码，便于对照报告理解算法落地与测试用例设计。当前已有1287人学习下载，适合用作课程设计模板、实验参考或答辩前梳理材料。

1. 从一份课程设计说起：NFA 空闭包到底要用代码做什么

手算一遍 ε-closure(I) 不难，难的是算到第十几个状态子集时还能保证不漏一条 ε 弧。编译原理课上讲子集构造，黑板上一画就过去了，真让你用 Java 把它落成一个能读文件、能输出全部状态子集、还能画出状态转换图的程序，多数人会卡在两处：递归求闭包时结果收不全，以及从字符串里抠状态名时下标对不上。这份《编译原理 ε-closure（I）的程序实现》课程设计报告，就是一个完整的落地样本——输入任意 NFA 的状态转移函数，程序输出所有状态子集的空闭包、指定子集的空闭包，并渲染出自动机的状态转换图。它适合两类读者：正在做编译原理课程设计、需要一份 Java 参考实现的学生；以及想复习子集构造细节、看看 move 和 ε-closure 这两步在代码里怎么拆的开发者。代码量不大，坑却不少，值得逐行拆开看。

2. 工程结构与数据模型：NFA 怎么被读进内存

这个项目没有上框架，也没有引入第三方依赖，一个 JDK 加几个 .java 文件就够跑。正因为简单，它把「输入用什么格式表达」「状态子集用什么结构存」这两个决定后续所有代码形态的问题摆在了台面上。先看骨架，再看数据。

2.1 目录、运行方式与输入文件格式

报告里的程序是控制台应用，类分得比较散：入口一个 Main，工具方法一个 Utils，剩下的是算法函数。按一线开发的习惯整理成下面这样，跑起来最省事：

# 目录结构（按实际代码整理） nfa-closure/ ├── src/ │ ├── Main.java # 入口：读文件、调度各模块 │ ├── Utils.java # 字符串与数组互转、格式化输出 │ └── Closure.java # 读空、读字母、求子集 ├── data/ │ └── nfa.txt # 输入的 NFA 定义 └── out/ # 编译产物

编译和运行只需要两条命令，注意-encoding UTF-8，输入文件里有 ε 这个字符，不指定编码在部分环境下会读成乱码，进而让后面的字符比较全部失效——这个坑后面还会细说。

javac -encoding UTF-8 -d out src/*.java java -cp out Main data/nfa.txt

输入文件的格式是三条内容拼起来的：第一行是全部状态，第二行是字母表，之后每行一条产生式。下面这份对应报告里的例子一：

X,1,2,3,4,5,6,Y a,b (X,ε)→5 (5,a)→5 (5,b)→5 (5,ε)→1 (1,a)→3 (1,b)→4 (3,a)→2 (4,b)→2 (2,ε)→6 (6,a)→6 (6,b)→6 (6,ε)→Y

读文件这一步没有太多花样，按行 split，第一行按逗号拆成状态数组，第二行拆成字母表，剩下的原样塞进String[] functionStrings。这里有一个隐含约定必须记住：状态名和字母都只占一个字符。整个项目的解析逻辑建立在这个前提上，一旦你把状态命名成q0、q10，解析就全线崩，具体原因见 2.2 节。

2.2 产生式的字符串表示与下标解析

报告里最「省事」也最脆的一处设计，是把一条转移关系当成定长字符串(1,a)→3来对待，然后用charAt按下标取字段。位置约定是这样的：

于是strings[i].charAt(1)取源状态，charAt(3)取字母，charAt(6)取目标状态。代码里到处是这种写法：

// 判断产生式 strings[i] 是不是从 string 的最后一个字符出发的 ε 弧 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)); } }

这段逻辑的意图很清楚：拿当前状态的最后一个字符，去和每条产生式的源状态（下标 1）比，相等再看字母位（下标 3）是不是 ε，是就把目标状态（下标 6）追加进来。问题在于它对输入格式的假设太硬——状态必须是单字符、箭头必须是单个→字符、括号和逗号一个都不能少。少一个空格没问题，多一个空格（比如(1, a)→3）就会让字母位变成空格，整个匹配静默失效，程序不报错但结果错，最难查。

我一般会把这种定长下标解析换成一次正则拆分，规则在启动时编译一次，后续只做字段比较，既快又不会因为格式微调翻车：

import java.util.regex.*; // 一条产生式：(源状态,字母)→目标状态，中间允许有空白 private static final Pattern RULE = Pattern.compile("^\\(\\s*(.+?)\\s*,\\s*(.+?)\\s*\\)\\s*→\\s*(.+?)\\s*$"); /** * 把 "(1,a)→3" 拆成 ["1", "a", "3"] * group(1) 源状态，group(2) 字母（ε 也在此列），group(3) 目标状态 * 返回 null 表示这行不合法，调用方跳过并提示行号 */ public static String[] parseRule(String line, int lineNo) { Matcher m = RULE.matcher(line); if (!m.find()) { System.err.println("第 " + lineNo + " 行格式不对，已跳过: " + line); return null; } return new String[]{ m.group(1), m.group(2), m.group(3) }; }

用String[]而不是自定义类，是为了和原代码里的String[] functionStrings平滑对接；如果你想更彻底一点，定义一个record Rule(String from, String symbol, String to)会让后面所有r[0].equals(...)变成r.from().equals(...)，可读性直接上一个台阶，而且状态名多字符也没问题。这一步改造的成本不到半小时，收益是后面所有算法函数都不用再关心格式。

2.3 数组、哈希表与 Set 在程序里各管什么

报告里写「主要用到数组、图以及哈希表」，落到代码上是三类容器，各司其职：

• String[] functionStrings：一次性读入的全部产生式，只读不改，遍历成本低，是这个规模下最合适的选择。
• Set<String>：表示一个状态子集 I。选 Set 而不是 List 的理由很实在——子集构造里要频繁判断「这个状态子集是否已经出现过」，用Set<Set<String>>的contains就是 O(1) 级别的哈希比较，而且 Set 的equals与元素顺序无关，{1,2,3}和{3,1,2}会被认为是同一个子集，正好符合数学定义。
• Map<Set<String>, Set<String>>：把每个状态子集映射到它的空闭包，最后一次性输出。

主循环里驱动子集展开的那层结构，报告用的是 map 加迭代器，其实换成双端队列更顺手：

import java.util.*; Set<Set<String>> dstates = new LinkedHashSet<>(); // 已发现的全部子集，保序 Deque<Set<String>> work = new ArrayDeque<>(); // 待处理队列 Set<String> start = Closure.closure(Set.of("X"), rules); dstates.add(start); work.add(start); while (!work.isEmpty()) { Set<String> I = work.poll(); for (String a : alphabet) { Set<String> next = Closure.closure(Closure.move(I, a, rules), rules); if (next.isEmpty()) continue; // 空集不入表，和报告的约定一致 if (dstates.add(next)) work.add(next); // add 返回 true 说明是新子集 } }

这里用LinkedHashSet而不是HashSet，是因为最后的输出要给人看。HashSet的迭代顺序依赖哈希值，同一份输入两次运行可能打出不同的顺序，调 bug 时会让你怀疑人生——明明代码没改，输出怎么变了。LinkedHashSet按插入顺序迭代，TreeSet按字典序，两者都比HashSet适合做「有输出」的集合。

提示：状态 ID 如果用String存，排序是按字典序的，"10"会排在"2"前面。要输出好看，可以在打印时套一个比较器，按数值排。

3. 三个函数撑起 ε-closure：从 X 的闭包到全部状态子集

整个项目的算法核心其实只有三件事：给一个状态求它的 ε 闭包、给一个子集读一个字母做 move、把这两步串成子集构造。报告作者在「详细设计」里反复强调的一句话很到位：读字母前后都要考虑读空，否则经过 a 又经过 ε、或者先 ε 再 a 的情况就漏了。下面按调用顺序拆。

3.1 先给 NFA 加一个初态 X 和一个终态 Y

子集构造的标准做法是给 NFA 补一个唯一初态 X，用 ε 弧连到原来的所有初态；再补一个唯一终态 Y，让原来所有终态用 ε 弧连到 Y。这样做的好处是 DFA 的初态就是 ε-closure({X})，不用特判「有多个初态怎么办」。

报告里对这一步做了简化：X 只连到非空初态集合中的某一个状态，Y 同理只从一个终态连过来，并且直接把这两条 ε 弧写进状态转移函数里，当作普通产生式处理。作者自己也说了，当时觉得「引一条空弧到任意一个状态节点」写起来太麻烦，往下做就做不下去了。这个取舍在课程设计的语境下可以理解——它不影响闭包算法的正确性，只是丢掉了「多初态/多终态」的通用性。如果你要拿去处理真实自动机，把 X 连到所有初态、所有终态连到 Y，只是往rules里多 push 几条记录的事：

// 补唯一初态 X 与唯一终态 Y，多初态/多终态都能覆盖 List<String[]> rules = new ArrayList<>(parsedRules); for (String s : initialStates) rules.add(new String[]{"X", "ε", s}); for (String s : finalStates) rules.add(new String[]{"ε" == null ? s : s, "ε", "Y"});

参数说明：initialStates是从输入文件里读出来的原始初态集合，finalStates是原始终态集合。注意这里不要在原来的functionStrings上原地改，拷贝一份再追加，否则重复运行会重复追加，X 的出边越跑越多——这是我在类似项目里真实翻过的车。

3.2 对 X 读空：递归求第一个状态子集

补完 X 之后，第一个状态子集就是 ε-closure({X})。报告里为此单独写了一个函数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; }

先说参数：string是「已经收集到的状态串」，初始传"X"；strings是全部产生式。返回值是扩展后的状态串。

这段代码有两个必须点出来的问题。第一，Java 的String是不可变对象，string += c等价于string = string + c，改的是当前栈帧的局部变量；递归调用RestltList(string, strings)里继续拼接，只影响递归那一层的局部变量，函数返回后这个新串就被丢掉了。结果就是闭包只扩了一层，X→5→1→3这种链式 ε 路径收不全。第二，如果 ε 弧构成环（比如1→2、2→1），递归没有任何判重，直接栈溢出。

修法有轻有重。轻的改一行，把返回值接住：

string = RestltList(string + strings[i].charAt(6), strings);

重的（也是我推荐的）是彻底放弃字符串拼接，用「集合 + 显式栈」的迭代写法，天然判重、天然没有递归深度问题：

/** * 求 states 的 ε 闭包 * @param states 起始状态集合，闭包结果一定包含其中每个元素 * @param rules 全部产生式，元素形如 [源状态, 字母, 目标状态] * @return 闭包集合，用 LinkedHashSet 保证输出顺序稳定 */ public static Set<String> closure(Set<String> states, List<String[]> rules) { Set<String> result = new LinkedHashSet<>(states); // 闭包首先包含自己 Deque<String> stack = new ArrayDeque<>(states); while (!stack.isEmpty()) { String cur = stack.pop(); for (String[] r : rules) { // 源状态匹配、字母是 ε、且目标状态是新的，才入栈 if (r[0].equals(cur) && "ε".equals(r[1]) && result.add(r[2])) { stack.push(r[2]); } } } return result; }

result.add(r[2])的返回值在这里承担了两个职责：既判断「是不是新状态」，又顺手完成了去重。环状 ε 弧在第二次访问同一状态时add返回 false，循环自然收敛。这套写法的时间复杂度是 O(|状态| × |产生式|)，课程设计里几十条产生式跑起来毫无压力。

3.3 只读字母的 Ia：move 函数的极简版

有了闭包函数，接下来要给一个状态子集读一个字母。报告里对应的是RestltListA，输入三个参数：状态子集、待读字母、全部产生式，输出读完之后到达的状态串。

// 报告原实现 public static String RestltListA(String string, String s, String[] strings) { String resultA = ""; for (int i = 0; i < strings.length; i++) { 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是单个状态（注意这里传的不是子集，报告在调用处对子集做了外层循环），s是要读的字母，strings是产生式数组。逻辑就是「源状态等于当前状态、字母等于 a，就把目标状态拼进去」。

这段代码本身没有致命问题，只是把「一个子集的 move」拆成了外层循环加单状态函数，调用方要自己套两层。换成集合版本更直观，也顺便解决了结果重复的问题：

/** * move(I, a)：子集 I 中所有状态经过字母 a 直达的状态集合 * 不包含 ε 闭包，闭包在外面套 */ public static Set<String> move(Set<String> states, String symbol, List<String[]> rules) { Set<String> result = new LinkedHashSet<>(); for (String s : states) { for (String[] r : rules) { if (r[0].equals(s) && r[1].equals(symbol)) { result.add(r[2]); } } } return result; }

注意这里不能判断 ε——move 只处理字母弧，闭包那一层另外算。报告作者在「6 总结」里写过一句很有价值的体会：一开始想把读空和读字母塞进一个函数，纠结很久写不出来；后来拆成两个函数，求子集的时候按「读空、读 a、再读空」的顺序串起来，逻辑一下子就清楚了。这个拆法就是标准的 ε-closure(move(I, a))，教科书上的公式和代码里的调用顺序一一对应。

3.4 读空、读 a、再读空：子集构造主循环

把前两个函数拼起来，就得到一条完整的推进规则。报告里写得很直白：求 Ia 不只是看 a 弧，还要看 a 弧到达的状态能不能再走 ε 弧到别处，所以读字母前后都要读空。对应到代码是三层：

// 计算 ε-closure(move(I, a)) Set<String> moved = move(I, a, rules); // 第一层：只读 a Set<String> closed = closure(moved, rules); // 第二层：对结果读空 // 如果还要考虑"先读空再读 a"的情况，I 本身应当已经是闭包

第三层的「读 a 之前读空」其实藏在主循环里：work队列里存的每个I都是上一轮closure(...)的产物，本身就是闭包，所以进入move之前不用再补。这也解释了为什么报告里DuKong那个函数传的参数是「子集读 a 之后的结果」而不是原始子集——它只补后半个闭包。理解这一点，DuKong和RestltList看起来重复的问题就不成立了，它们作用于链路上的不同位置。

完整的主循环在 2.3 节已经给过，这里补上「输出指定状态子集的空闭包」这个需求的落点。报告的基本要求里有一条是「输出给定状态子集的空闭包」，实现上就是遍历输入字符，把用户给的子集构造出来，直接调closure：

// 用户输入的 I，例如 "1,3" Set<String> query = new LinkedHashSet<>(Arrays.asList(input.split(","))); Set<String> answer = closure(query, rules); System.out.println("ε-closure(" + query + ") = " + answer);

参数说明：input是从控制台读的一行，逗号分隔；closure内部会先把query的元素全部塞进结果，所以 I 里的状态一定出现在答案里，符合闭包「包含自身」的定义。如果用户输入了不存在的状态，closure不会报错，只会原样返回，这一点在交互时最好加一句校验，把非法状态提前拦下来。

4. 状态转换图输出：把转移函数画成能看懂的图

报告的第四个基本要求是「以状态转换图方式输出用户输入的有限自动机，要求状态结点大小位置布局合理，具有通用性」。这一块常常被当成加分项糊弄过去，实际上它比算法更考验工程判断：结点位置是算出来的还是写死的，直接决定了换个输入会不会糊成一团。

4.1 结点布局：先定层，再定坐标

最省事的画法是把所有结点摆在一个圆上，半径随结点数增长。这种做法对课程设计规模的自动机（十个上下状态）足够，而且「通用性」天然满足——不管输入几个状态，坐标都由公式算，不写死。

/** * 环形布局：把 n 个状态均匀摆在一个圆上 * @param states 全部状态，顺序决定谁在圆周的哪个位置 * @return 状态名 -> [x, y] 坐标 */ public static Map<String, int[]> ringLayout(List<String> states) { int n = states.size(); int radius = Math.max(140, 36 * n); // 结点越多，圆越大 int cx = radius + 60, cy = radius + 60; // 圆心，留出边距 Map<String, int[]> pos = new LinkedHashMap<>(); double step = 2 * Math.PI / n; for (int i = 0; i < n; i++) { double theta = -Math.PI / 2 + i * step; // 从正上方开始摆 pos.put(states.get(i), new int[]{ (int) Math.round(cx + radius * Math.cos(theta)), (int) Math.round(cy + radius * Math.sin(theta)) }); } return pos; }

参数说明：radius取36 * n和 140 的较大值，保证结点之间至少留出约一个结点直径的间隙；-Math.PI / 2的起始角让第一个状态落在正上方，视觉上有明确的「入口」感。这套公式的代价是边会互相穿插，但结点本身不会重叠，满足「布局合理」的最低要求。真要讲究，可以改成层次布局：BFS 从 X 出发算每个状态的层号，同层水平排开，层间垂直拉开，边的走向会干净得多，代价是遇到不可达状态要单独处理。

4.2 Swing 画布与 Graphviz 两条路线

报告里选的是 Swing 直接画，一个JPanel重写paintComponent，用Graphics2D先画边后画结点。核心代码不长：

@Override protected void paintComponent(Graphics g) { super.paintComponent(g); Graphics2D g2 = (Graphics2D) g; g2.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON); g2.setStroke(new BasicStroke(1.6f)); int r = 22; // 结点半径 // 先画边，避免边压住结点文字 for (String[] rule : rules) { int[] a = pos.get(rule[0]), b = pos.get(rule[2]); if (a == null || b == null) continue; g2.setColor(Color.GRAY); g2.drawLine(a[0], a[1], b[0], b[1]); // 标签画在中点偏上的位置，简单避让 g2.setColor(Color.DARK_GRAY); g2.drawString(rule[1], (a[0] + b[0]) / 2, (a[1] + b[1]) / 2 - 4); } // 后画结点 for (Map.Entry<String, int[]> e : pos.entrySet()) { int[] p = e.getValue(); g2.setColor(new Color(0xF2F6FC)); g2.fillOval(p[0] - r, p[1] - r, r * 2, r * 2); g2.setColor(new Color(0x33507A)); g2.drawOval(p[0] - r, p[1] - r, r * 2, r * 2); g2.drawString(e.getKey(), p[0] - 6, p[1] + 5); } }

参数上要注意三点：r是结点半径，文字用drawString居中时要减去大约一半字宽、加上约 5px 的基线偏移；paintComponent里不要改全局状态后不还原，Swing 会复用Graphics对象；密集图里中点标签一定重叠，最少也要按边方向偏移几像素。

另一条路线是生成.dot文件交给外部渲染，几十行代码，布局质量却高得多，尤其是边多的时候：

/** * 生成 Graphviz dot 文本，重定向到文件后用 dot -Tpng 出图 */ public static String toDot(List<String> states, List<String[]> rules) { StringBuilder sb = new StringBuilder("digraph NFA {\n rankdir=LR;\n node [shape=circle];\n"); for (String s : states) sb.append(" \"").append(s).append("\";\n"); for (String[] r : rules) { sb.append(" \"").append(r[0]).append("\" -> \"").append(r[2]) .append("\" [label=\"").append(r[1]).append("\"];\n"); } return sb.append("}\n").toString(); }

rankdir=LR让图从左往右排，比默认的自上而下更接近自动机的阅读习惯。这份输出的价值在于「可复现」——同一份 NFA 任何时候生成的图一模一样，方便写进报告。

4.3 边的细节：自环、多重边与 ε 标签

真正让图画得难看的不是布局，是边的细节处理。三件事必须提前想清楚：

自环。(5,a)→5这种边如果直接drawLine，长度为零，什么都看不见。常见做法是从结点上方引一个小圆弧再绕回来：

// 自环：以结点正上方为顶点画一段二次曲线 if (rule[0].equals(rule[2])) { int[] p = pos.get(rule[0]); g2.drawArc(p[0] - 14, p[1] - r - 22, 28, 26, 0, 360); g2.drawString(rule[1], p[0] - 4, p[1] - r - 26); continue; }

多重边。两个状态之间既有一条 a 弧又有一条 b 弧时，两条直线完全重合，标签叠在一起。简单的解法是把第 k 条平行边整体平移k * 6像素，或者改成曲线并控制弯曲度。

ε 标签。输入文件里写的是希腊字母 ε，Swing 默认字体能不能显示要看系统。稳妥做法是设一个支持希腊字母的字体（如Dialog），或者在渲染时把ε替换成e并在图例里说明。这一点在报告里没有提，但在实际运行时是肉眼可见的差异——标签位置出现一个空心方块，多半就是这个原因。

注意：drawString画中文状态名在部分环境会走字形回退，字号和位置都得重新量，别沿用单字符时的那套偏移量。

5. 踩坑排查：字符串递归与集合遍历的五个翻车现场

这个项目的代码量撑死几百行，但我在复现和改造的过程中踩到的坑密度不低，而且每一个都不是「写错了报个错」那么友好，多数是不报错但结果不对。下面五条按「现象 → 原因 → 解决」组织，都是可以直接对照自己代码的。

5.1 闭包只扩了一层，长 ε 链收不全

现象：输入(X,ε)→5 (5,ε)→1 (1,ε)→3，期望ε-closure(X) = {X,5,1,3}，实际只得到{X,5}，程序正常退出，没有任何异常。

原因：RestltList里写了string += ...之后调RestltList(string, strings)，但没接返回值。Java 的String不可变，+=只是把当前栈帧的局部变量指向新串，递归里再拼出来的东西返回后就被丢了，实际只生效了最外层一次。

解决：要么把返回值接住string = RestltList(string + c, strings)，要么直接换成 3.2 节那套「Set + 栈」的迭代写法。我现在的习惯是：只要函数里出现递归改字符串，第一反应就是换成可变容器，省得下次又忘。

5.2 ε 环把递归打成栈溢出

现象：输入里存在(1,ε)→2 (2,ε)→1，运行几秒后抛StackOverflowError，栈帧全是同一个函数名。

原因：递归实现没有任何「访问过」标记，环上的两个状态互相触发，无限深入。

解决：加一个visited集合，每进一个状态先if (!visited.add(s)) return;。用 3.2 节的迭代版本连改都不用改，result.add(r[2])的返回值本身就是判重逻辑。

5.3 状态名换成多字符立刻数组越界

现象：把输入里的状态从1、2改成q1、q2，程序在strings[i].charAt(6)处抛StringIndexOutOfBoundsException，或者不抛异常但读出来的目标状态是半个名字。

原因：解析用的是定长下标，charAt(1)取源状态、charAt(3)取字母、charAt(6)取目标态，全部建立在「状态名和字母都只占一个字符」这个前提上。状态名一变长，后面所有字段的位置全部右移。

解决：用 2.2 节的正则拆分代替charAt。这一步越早做越好，等到算法写完再改，所有函数都得跟着动。

5.4 一边遍历 Set 一边往里加，抛并发修改异常

现象：求「所有状态子集的空闭包」那段，偶尔抛ConcurrentModificationException，重跑一次可能又不抛了。

原因：外层用Iterator遍历状态子集，内层调用的读空函数如果直接往同一个集合里add，迭代器的modCount就对不上。这类 bug 的恶心之处在于「偶发」——取决于哈希顺序和元素个数，测试时跑十次过一次。

解决：所有「遍历 + 扩展」的地方，都把新元素收进一个独立的临时集合，遍历结束后再addAll回去。或者干脆换成Deque驱动的工作队列，天然避开迭代器失效。

5.5 两次运行输出顺序不一样，误以为算法有随机性

现象：同一份输入连跑两次，状态子集的打印顺序变了，肉眼看不出规律，一度怀疑是某处用了随机数。

原因：HashSet的迭代顺序由元素的哈希值决定，而字符串的哈希是稳定的——问题出在状态子集本身是Set<String>，Set的hashCode是元素哈希之和，元素多了以后桶分布变化，遍历顺序就跟着变。程序没错，是输出没做归一化。

解决：存状态子集用LinkedHashSet保留插入顺序，打印之前再套一层TreeSet按名字排序。调 bug 阶段这一步不能省，输出稳定了才谈得上对比两次运行的结果。

提示：这五个坑里有四个的共同特征是「不抛异常、结果悄悄错」。写这类算法程序，断言比打印更有用——每求出一个子集就断言它包含自己的所有 ε 后继，错了当场停。

6. 二次开发：把课程级代码改成能用的子集构造工具

这份代码作为课程设计是合格的，逻辑讲清楚了，测试用例也覆盖了带环、带空集、带多终态几种情况。但要拿去做二次开发，我建议按下面的顺序动刀，收益从高到低：

改造的验证方法很简单，也很有效：自己手写三组 NFA，一组纯 ε 链、一组带 ε 环、一组带不可达状态，把程序输出和手算结果逐行对。特别是不可达状态那一组——子集构造从 X 出发，永远走不到的状态不会出现在dstates里，如果你的输出里出现了，说明驱动循环写错了。

如果想再往前走一步，把「状态子集 → 空闭包」的映射顺手做成 DFA 的转移表，这个项目就能直接给词法分析器当后端用：DFA 的每个状态对应一个Set<String>，转移表就是Map<Set<String>, Map<String, Set<String>>>，输入一个字符查一次表。报告里已经把这个映射mapmax建出来了，只是拿去打印而没有继续用，稍微改几行就能接上。

最后一个技巧，关于「读空、读 a、再读空」这个顺序。很多人第一次写会想着把三步揉进一个函数，包括报告作者自己也说在这上面纠结了好一阵。我的经验是死死守住closure(move(I, a))这个公式，一个函数只干一件事，调用处把顺序写死，别想着优化。真出问题时，你能一眼看出是 move 错了还是 closure 错了；揉在一起就只能靠打印大法慢慢试。

这份报告我是当成一面镜子看的——它记录的那些纠结，我自己一行行写的时候一个不落地重新纠结了一遍。从那以后我每次写递归求闭包，第一件事就是先把判重的 Set 建出来，再动循环，算是给自己留的后悔药。希望帮到你。

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