简介：这是一份面向计算机专业学生的编译原理课程设计报告，围绕有限自动机空闭包 ε-closure(I) 的 Java 程序实现展开，适合正在完成课程设计、实验或准备复习 NFA 状态子集构造的读者参考。报告从需求分析与概要设计入手，介绍数组、图结构和哈希表等数据组织方式，并拆解读空函数、状态子集扩展、读字母表等模块；详细设计部分说明引入新初态 X、终态 Y 后，如何通过递归逐条处理空弧并累加结果，最终输出全部状态子集及指定子集的空闭包，同时以状态转换图呈现自动机结构。正文还包含测试样例、用户使用说明与总结，能帮助读者理解算法流程、对照实现思路并排查递归终止与状态扩展中的问题。资源包共 1 个 docx 文件，约 177KB，为可查阅和修改的课程设计文档。已有 1287 人学习，适合作为课程设计写作与 ε-closure 编程实现的对照材料。

1. ε-closure(I) 到底在算什么：一份 Java 课程设计报告的复现起点

编译原理课设里，ε-closure(I) 是那种老师讲十分钟、自己写三天还错的地方。这份 Java 课程设计报告做的事情很明确：读入一个任意给定的 NFA，把状态子集一路推出来，对每个子集求空闭包，并把自动机按状态转换图画出来，结点位置要求「布局合理、有通用性」。它适合两类人——正在赶课设、需要一个能跑通骨架的，以及想把子集构造法从伪代码落到真实数据结构上的。后面按「数据怎么进来、闭包怎么算、图怎么画、哪里会翻车」的顺序拆，代码在报告原有函数基础上改写成可直接编译的版本，手上有 JDK 就能跟。

2. 把 NFA 读进内存：产生式编码、数据契约与三个函数的职责边界

这份报告最容易被低估的部分不是算法，是数据怎么进来。原文把状态转移写成(1,a)→3这样的字符串，然后靠charAt(1)、charAt(3)、charAt(6)三个固定下标去抠源状态、字母和目标状态。这个做法在课设里能跑通，因为它默认了三件事：状态名只有一个字符、字母只有一个字符、箭头和括号的写法一个字都不能变。三件事只要破一件，整个程序就在解析层崩掉，而且崩得很隐蔽——不会抛异常，只会算出一个静悄悄的错误结果。

我一般会把输入切成「段标记 + 逗号分隔」的文本格式，把解析和算法彻底分开。原因很实在：闭包算法是稳定的，输入格式是随时会变的，两者耦合在一起，改一次输入就得动一遍算法，调试成本翻倍。

2.1 文件格式与状态转移的存储结构

先定数据契约。下面这份nfa.txt是后面所有代码的输入，$代表 ε 弧，段标记以@开头：

@states q0,q1,q2,q3 @alphabet a,b @start q0 @accept q3 @trans q0,$,q1 q1,a,q2 q2,$,q3 q3,b,q3

对应的两个基础类型，Transition只存三个字段，不做任何解析；Nfa负责集合与索引：

import java.util.*; /** 一条状态转移：from --symbol--> to；symbol 为 "$" 时代表 ε 弧 */ final class Transition { final String from; final String symbol; final String to; Transition(String from, String symbol, String to) { this.from = from; this.symbol = symbol; this.to = to; } @Override public String toString() { return from + " -" + symbol + "-> " + to; } } final class Nfa { final Set<String> states = new LinkedHashSet<>(); final Set<String> alphabet = new LinkedHashSet<>(); final Set<String> starts = new LinkedHashSet<>(); final Set<String> accepts = new LinkedHashSet<>(); final List<Transition> transitions = new ArrayList<>(); /** 源状态 -> 出边列表，避免每次求闭包都全表扫一遍 */ private final Map<String, List<Transition>> index = new HashMap<>(); void buildIndex() { index.clear(); for (Transition t : transitions) { index.computeIfAbsent(t.from, k -> new ArrayList<>()).add(t); } } List<Transition> outOf(String state) { return index.getOrDefault(state, Collections.emptyList()); } }

这里用LinkedHashSet而不是HashSet，理由不是性能，是可复现：同一份输入跑两次，输出的状态顺序必须一致，否则你没法用 diff 对比「改代码前」和「改代码后」的结果差异。子集构造这种指数级输出的东西，顺序一乱，人工核对基本等于重做。

buildIndex把「按源状态取出边」从 O(m) 降到 O(1)。原文的几个函数都是「外层循环状态、内层循环全部产生式」，状态数上到二十、弧数上到五十以后，子集构造里每产生一个新子集就要扫一遍全表，卡顿会非常明显。课设规模小感觉不到，但这是一种会随着输入规模放大的写法，早改早省事。

解析器本身没有技术含量，关键是每一段都必须给出明确的失败信息：

import java.io.*; import java.nio.charset.StandardCharsets; static Nfa parse(File file) throws IOException { Nfa nfa = new Nfa(); int section = 0; // 0=未进入任何段 try (BufferedReader br = new BufferedReader( new InputStreamReader(new FileInputStream(file), StandardCharsets.UTF_8))) { String line; while ((line = br.readLine()) != null) { line = line.trim(); if (line.isEmpty() || line.startsWith("#")) continue; // 注释与空行跳过 if (line.startsWith("@")) { switch (line.substring(1)) { case "states": section = 1; break; case "alphabet": section = 2; break; case "start": section = 3; break; case "accept": section = 4; break; case "trans": section = 5; break; default: throw new IllegalArgumentException("未知段标记：" + line); } continue; } String[] p = line.split("\\s*,\\s*"); // 逗号两侧允许空格 switch (section) { case 1: nfa.states.addAll(Arrays.asList(p)); break; case 2: nfa.alphabet.addAll(Arrays.asList(p)); break; case 3: nfa.starts.add(p[0]); break; case 4: nfa.accepts.add(p[0]); break; case 5: if (p.length != 3) { throw new IllegalArgumentException("转移行必须是 源,符号,目标：" + line); } nfa.transitions.add(new Transition(p[0], p[1], p[2])); nfa.states.add(p[0]); // 转移里出现但没声明的状态自动补登记 nfa.states.add(p[2]); break; default: throw new IllegalArgumentException("数据行出现在任何段标记之前：" + line); } } } nfa.buildIndex(); return nfa; }

section是一个状态机，switch里每个分支只做一件事。p.length != 3这一行是必须的：没有它，少写一个逗号就会抛ArrayIndexOutOfBoundsException，报错行号指向数组访问而不是你的数据文件，排查时间全浪费在找错地方。参数上唯一需要留意的是文件编码，InputStreamReader显式指定UTF-8，后面第 5 章会讲到不指定会出什么事。

2.2 读空、读字母、读后再读空：三段式函数的输入输出

原文把闭包拆成三个函数，这个拆法本身是对的，只是名字起得随意。放到标准子集构造的语境里，它们是三个语义清晰的算子：

原文说的「读空、读 a、再读空」其实比标准定义多做了一次前置读空。多出来的那一次不是错误，是冗余：参与运算的子集如果已经是闭包，前置读空的结果就是它自己。但冗余会带来一个副作用——当你想单独测试闭包函数是否正确时，喂进去的集合本身已经是闭包，输出和输入一模一样，你根本判断不出函数有没有生效。这个现象在第 5 章会展开。

三个函数的实现极短，短到没有出错空间：

/** ε-closure：栈式不动点，visited 兼作结果集，天然去重 */ static Set<String> epsilonClosure(Nfa nfa, Collection<String> seed) { Set<String> closure = new LinkedHashSet<>(seed); // 闭包恒包含自身 Deque<String> stack = new ArrayDeque<>(seed); while (!stack.isEmpty()) { String cur = stack.pop(); for (Transition t : nfa.outOf(cur)) { if (!"$".equals(t.symbol)) continue; // 只走 ε 弧 if (closure.add(t.to)) stack.push(t.to); // add 返回 false 说明已收过，不再展开 } } return closure; } /** move：只走字母弧，不看 ε */ static Set<String> move(Nfa nfa, Collection<String> set, String symbol) { Set<String> result = new LinkedHashSet<>(); for (String s : set) { for (Transition t : nfa.outOf(s)) { if (symbol.equals(t.symbol)) result.add(t.to); } } return result; } /** 子集构造里真正用到的一步 */ static Set<String> step(Nfa nfa, Collection<String> set, String symbol) { return epsilonClosure(nfa, move(nfa, set, symbol)); }

if (closure.add(t.to)) stack.push(t.to);这一行是整个闭包函数的核心。Set.add返回布尔值，返回true表示这是个新状态，值得继续展开；返回false表示之前已经收过，再展开就是重复劳动甚至死循环。用add的返回值当去重判据，比先contains再add少一次哈希查找，更重要的是它把「去重」和「是否继续」绑成了一个原子判断，不会出现「判断了没加、加了没判断」这类经典笔误。ε 环在真实 NFA 里非常常见，比如q0 -ε-> q1、q1 -ε-> q0，没有这个判据就是StackOverflowError。

2.3 子集构造的主循环与不动点终止

有了step，主循环就是一个标准的宽度优先搜索，队列里放的是集合而不是状态：

/** 返回子集构造过程中产生的全部状态集合，顺序稳定 */ static List<Set<String>> buildSubsets(Nfa nfa) { Set<Set<String>> visited = new LinkedHashSet<>(); // Set 的 hashCode 与元素顺序无关，可直接去重 Deque<Set<String>> queue = new ArrayDeque<>(); Set<String> start = epsilonClosure(nfa, nfa.starts); // 新初态的闭包 = 所有初态闭包的并 visited.add(start); queue.add(start); while (!queue.isEmpty()) { Set<String> cur = queue.poll(); for (String a : nfa.alphabet) { Set<String> next = step(nfa, cur, a); if (next.isEmpty()) continue; // 空集是否保留成死状态，看课程要求 if (visited.add(next)) queue.add(next); // 只有新集合才入队，这就是不动点判据 } } return new ArrayList<>(visited); }

visited.add(next)既做去重又做「是否入队」的判定，和闭包函数里是同一个套路。子集数量最多 2 的 n 次方，但实际 NFA 通常远小于这个上界，因为很多子集根本不可达。next.isEmpty()那一行的取舍取决于课设要求：如果要求画出完整 DFA，需要保留一个死状态；如果只要求输出可达子集，直接跳过。这一点在写报告的时候要明确写出来，否则答辩时被问「你的 DFA 为什么少一个状态」会很被动。

buildSubsets返回List而不是Set，是因为后面输出、画图、建转移表都要按下标访问，List用起来直接。顺序由LinkedHashSet的插入序保证，也就是按 BFS 发现的顺序，这个顺序对人读输出是友好的。

3. 递归求闭包：String 累加的翻车现场与 Set 版本重写

原文所有闭包逻辑都靠递归加字符串拼接完成，还特意提到「用静态变量字符串接收结果」。这段代码我第一眼看到就觉得不对劲，实际跑起来会发现它不是「偶尔出错」，而是稳定地少收状态。原因不复杂，但很值得写下来，因为它踩的是 Java 里最基础也最容易被忽略的一条：方法参数是值传递，String不可变。

3.1 为什么第一版用递归，以及递归错在哪

原文的读空函数长这样，逻辑意图是「一直递归到没有新状态为止」：

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; }

问题出在RestltList(string, strings);这一行——调用完就完了，返回值没赋给任何变量。string是局部变量，在方法入口处复制了一份引用的副本，递归调用把它再复制一份传给下一层。下一层里string += ...生成一个新对象并赋给下一层的局部变量，当前这一层手里的string完全没变。等递归返回，那个更长的字符串就随着栈帧一起被丢掉了。

最终效果是：闭包只收了一层。X -ε-> 5能查到，5 -ε-> 1查不到。如果 NFA 的 ε 链只有一层，函数看起来是对的；只要有二层以上，结果就是错，而且错得很安静。

同一段代码还有两个次要问题。string.charAt(string.length() - 1)只取最后一个字符，隐含「状态名是单字符」这个假设；string里如果拼进了多字符状态名，取到的是半个名字。另外整个函数没有 visited，q0 -ε-> q1加q1 -ε-> q0会直接把栈打穿。

注意：递归本身没问题，问题在「靠递归的副作用收集结果」。收集型递归要么把返回值接住再传入下一层，要么干脆传一个可变容器进去，两条路选一条，别混着来。

3.2 用 Set 收集器重写 ε-closure

改成迭代加Set之后，代码反而更短。第 2 章的epsilonClosure已经给出了版本，这里补一个带「来源追踪」的变体——调试的时候能直接看到某个状态是怎么被收进闭包的，省掉大量打印语句：

/** 返回 状态 -> 把它收进闭包的前驱状态，用于排查闭包为什么多/少 */ static Map<String, String> closureWithTrace(Nfa nfa, Collection<String> seed) { Map<String, String> from = new LinkedHashMap<>(); Deque<String> stack = new ArrayDeque<>(); for (String s : seed) { from.put(s, null); // 种子状态没有前驱 stack.push(s); } while (!stack.isEmpty()) { String cur = stack.pop(); for (Transition t : nfa.outOf(cur)) { if (!"$".equals(t.symbol)) continue; if (!from.containsKey(t.to)) { from.put(t.to, cur); // 记录是被谁拉进来的 stack.push(t.to); } } } return from; }

from的 key 集合就是闭包本身，value 是前驱，null表示种子。排查「闭包少了某个状态」的时候不用猜，看这个状态在不在 key 里、不在就顺着 ε 弧往回找断在哪一条；排查「闭包多了某个状态」也一样，顺着 value 链往上走，一眼能看出是不是某条ε弧被误读成了别的符号。参数seed接受Collection而不是Set，是为了让调用方可以直接传List，少一次装箱拷贝的麻烦。

3.3 从新增初态 X 求首个子集，批量输出闭包

标准子集构造会在 NFA 前面加一个新初态 X、后面加一个新终态 Y。原文在这一点上做了妥协，只让 X 连到「非空初态集里的某一个状态」，理由是「连到任意一个太麻烦」。这个妥协在单初态的 NFA 上完全看不出问题，在多初态 NFA 上会直接算错——剩下那几个初态的闭包根本进不了第一个子集。

我在实现里把这步改回完整语义：X 到每个初态都连一条 ε 弧，然后直接求epsilonClosure(nfa, nfa.starts)，等价于求 X 的闭包，还省掉了真的把 X 插进图里的麻烦。Y 同理，把所有终态收进一个集合，判断某个子集是否为终态时用「与终态集有交集」代替。

批量输出这一段是课设的要求之一，也是第 5 章那个「输出和输入一样」的坑的源头：

static void printAllClosures(Nfa nfa) { List<Set<String>> subsets = buildSubsets(nfa); System.out.println("状态子集\t空闭包"); for (Set<String> sub : subsets) { Set<String> closure = epsilonClosure(nfa, sub); // 标准构造下 sub 已是闭包，这里等于自身 System.out.println(sub + "\t" + closure); } }

跑起来会发现两列内容一模一样，很多人到这一步以为算法没生效，回头去改闭包函数，越改越乱。真相是buildSubsets产出的每个sub本身就是闭包，再求一次当然是它自己。要验证闭包函数，得拿原始状态（比如只含{q0}）单独喂进epsilonClosure，别拿子集构造的结果去测它。

4. 状态转换图：邻接表建模、分层布局与自环/双向边处理

报告里「以状态转换图方式输出、结点大小位置布局合理、具有通用性」这条要求，实际动手量比闭包算法还大。闭包是纯计算，画图要处理坐标、边重叠、自环、双向边、终态双圈，每一项都能卡半天。

4.1 图数据结构与边去重

画图之前先把「哪些边要画」算清楚。NFA 里同一对状态之间可能有多条不同符号的边，直接画会重叠成一团，正确做法是按 (源, 目标) 归并，把符号拼成一个标签：

/** 把 (from,to) 相同的多条转移合并成一条边，标签用逗号拼接 */ static List<String[]> mergeEdges(Nfa nfa) { Map<String, List<String>> byPair = new LinkedHashMap<>(); // key = from + "\u0001" + to for (Transition t : nfa.transitions) { String key = t.from + "\u0001" + t.to; String label = "$".equals(t.symbol) ? "ε" : t.symbol; byPair.computeIfAbsent(key, k -> new ArrayList<>()).add(label); } List<String[]> edges = new ArrayList<>(); for (Map.Entry<String, List<String>> e : byPair.entrySet()) { String[] parts = e.getKey().split("\u0001"); edges.add(new String[]{ parts[0], parts[1], String.join(",", e.getValue()) }); } return edges; }

用\u0001做分隔符而不是逗号或冒号，是因为状态名里可能出现任何可打印字符，只有控制字符能保证不冲突。这是个很小的习惯，但在解析类项目里能省掉一堆「状态名叫a:b怎么办」的追问。

4.2 分层坐标计算与结点半径

「布局合理」翻译成代码就是：层次分明、同行不重叠、整体居中。用 BFS 层次是最省事也最通用的做法，环形布局在状态数少的时候好看，状态一多就挤成一坨：

/** BFS 分层，同一层沿水平方向等距铺开；从初态不可达的状态单独沉到底层 */ static Map<String, int[]> layout(Nfa nfa, int width, int height) { Map<String, Integer> depth = new HashMap<>(); Deque<String> queue = new ArrayDeque<>(); for (String s : nfa.starts) { depth.put(s, 0); queue.add(s); } Map<String, List<String>> adj = new HashMap<>(); for (Transition t : nfa.transitions) { adj.computeIfAbsent(t.from, k -> new ArrayList<>()).add(t.to); } while (!queue.isEmpty()) { String cur = queue.poll(); int d = depth.get(cur); for (String to : adj.getOrDefault(cur, Collections.emptyList())) { if (!depth.containsKey(to)) { // 只按首次到达定层，回边不参与 depth.put(to, d + 1); queue.add(to); } } } int maxDepth = depth.values().stream().mapToInt(Integer::intValue).max().orElse(0); for (String s : nfa.states) depth.putIfAbsent(s, maxDepth + 1); // 兜底，防止缺坐标 Map<Integer, List<String>> layers = new TreeMap<>(); for (String s : nfa.states) { layers.computeIfAbsent(depth.get(s), k -> new ArrayList<>()).add(s); } Map<String, int[]> pos = new HashMap<>(); int rowCount = layers.size(), row = 0; for (Map.Entry<Integer, List<String>> e : layers.entrySet()) { List<String> nodes = e.getValue(); double y = (rowCount == 1) ? height / 2.0 : 60 + (height - 120.0) * row / (rowCount - 1); for (int i = 0; i < nodes.size(); i++) { double x = width * (i + 1.0) / (nodes.size() + 1); pos.put(nodes.get(i), new int[]{(int) x, (int) y}); } row++; } return pos; }

if (!depth.containsKey(to))这个判断很关键。状态图里回边极多，如果不加判断，BFS 每遇到一条回边就把目标状态的层次往上推，层数会一路涨到超过状态总数，图会被拉成一条斜线。只按首次到达定层，等价于对图做一次最短路径分层，视觉上最接近教科书画法。

结点半径建议按状态名的字符数动态算，r = max(18, 8 + textWidth / 2)，固定半径在状态名变长之后会出现文字压边框。同行间距用width / (n + 1)也能用，但当同层状态超过八个时，中点会被挤到一起，稳妥一点的做法是取max(固定间距, 可用宽度 / n)，超宽就允许横向滚动。

4.3 Swing 绘制与 DOT 导出

两条输出路线，看课设要求哪种。要求截图放进报告里，Swing 直接画最省事；要求可交互或可打印，导成 DOT 交给 Graphviz 渲染质量更高。

Swing 这边，paintComponent里只做三件事：画边、画结点、画标签。自环和双向边是两个必须单独处理的情况：

@Override protected void paintComponent(Graphics g) { super.paintComponent(g); Graphics2D g2 = (Graphics2D) g; g2.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON); for (String[] e : edges) { // edges 来自 mergeEdges int[] p1 = pos.get(e[0]), p2 = pos.get(e[1]); if (e[0].equals(e[1])) { g2.drawArc(p1[0] - 12, p1[1] - R - 24, 24, 24, 0, 360); // 自环画成小圆 g2.drawString(e[2], p1[0] + 16, p1[1] - R - 8); continue; } boolean back = hasReverse(e[0], e[1]); // 反向边是否存在，存在则画弧线错开 int offset = back ? 14 : 0; g2.drawLine(p1[0], p1[1] + offset, p2[0], p2[1] + offset); g2.drawString(e[2], (p1[0] + p2[0]) / 2, (p1[1] + p2[1]) / 2 - 6); } for (String s : pos.keySet()) { // 先画边后画点，保证点压在边上面 int[] p = pos.get(s); g2.drawOval(p[0] - R, p[1] - R, R * 2, R * 2); if (nfa.accepts.contains(s)) { // 终态套双圈 g2.drawOval(p[0] - R - 4, p[1] - R - 4, (R + 4) * 2, (R + 4) * 2); } g2.drawString(s, p[0] - 6, p[1] + 5); } }

hasReverse的实现就是查一下edges里有没有(e[1], e[0])。有的话两条边都往下偏移，视觉上分成两条弧。这个偏移量 14 是试出来的，太小两条线还是贴在一起，太大箭头会飘到结点外面。

导出 DOT 的代码只有十几行，适合直接贴进报告附录：

static String toDot(Nfa nfa) { StringBuilder sb = new StringBuilder("digraph NFA {\n rankdir=LR;\n node [shape=circle];\n"); for (String s : nfa.states) { String shape = nfa.accepts.contains(s) ? "doublecircle" : "circle"; sb.append(" \"").append(s).append("\" [shape=").append(shape).append("];\n"); } for (Transition t : nfa.transitions) { String label = "$".equals(t.symbol) ? "ε" : t.symbol; sb.append(" \"").append(t.from).append("\" -> \"").append(t.to) .append("\" [label=\"").append(label).append("\"];\n"); } return sb.append("}\n").toString(); }

rankdir=LR让图从左到右排，跟教材里的自动机图方向一致；doublecircle是 Graphviz 里终态的标准写法，不用自己套圈。文件名后缀写.dot，渲染交给外部工具，代码里不引任何图形库依赖，课设环境里少一个装包的环节。

5. 避坑与排查：五条踩坑记录，每条都能让结果错得毫无提示

这一章是整篇里我最想写的部分。前面几章的代码都是改好之后的样子，真正耗时间的是从「跑出来不对」到「知道哪里不对」这一段。下面五条都是我在本地照着原文复现时真实撞上的，共同点是：不报错、不崩溃、程序正常退出，只是结果悄悄错了。

5.1 闭包只收一层：String 在递归里被复制了

现象：ε 链X -ε-> 5 -ε-> 1，闭包输出{X, 5}，1死活进不来。换成只有一层 ε 的 NFA 又完全正常。

原因：递归调用RestltList(string, strings)的返回值没有被接住。String不可变，string += x在当层栈帧里创建新对象并赋给局部变量，父层手里那份引用指向的还是老对象。递归越深，被丢掉的部分越多。

解决：换成第 3 章的epsilonClosure，用Set做收集器，迭代代替递归。如果一定要保留递归形式，就得写成string = RestltList(string + next, strings); return string;，让每层都把结果接住再往下传。我倾向前者，一是没有栈深度风险，二是收集逻辑和遍历逻辑分开了，调试时能单独打断点看集合内容。

5.2 ε 符号读成乱码：编码没对齐

现象：数据文件里明明写的是ε，程序里"ε".equals(...)永远返回false，闭包只剩种子状态自己，一个都收不进来。

原因：源文件用 UTF-8 保存，javac在有的环境里默认按平台编码（GBK）读源文件，编译出来的字符串常量字节序列和运行时的ε对不上。表现出来就是「代码看着没错，结果就是不对」，最消耗耐心的一种。

解决：三处一起对齐。源文件保存为 UTF-8；编译加-encoding UTF-8；读数据文件时显式new InputStreamReader(in, StandardCharsets.UTF_8)。更彻底的做法是数据文件里干脆不用ε，用$或空串表示，只在输出、画图的时候再映射回ε，把编码风险限制在展示层。第 2 章的解析器用的就是这个思路。

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

5.3 输出的闭包和输入一模一样

现象：批量输出所有子集的闭包，两列内容完全相同，逐行对比零差异。以为是闭包函数没被调用。

原因：buildSubsets产出的每个子集本身就是「先 move 再求闭包」的结果，天然是闭包。再对它求一次闭包，由幂等性必然得到自身。这个现象恰恰说明算法是对的。

解决：验证闭包函数要拿非闭包的原始集合去测。准备三个最小用例：单状态无 ε 出口、两层 ε 链、两个状态互为 ε 环。三个都过，再跑完整 NFA。另外在输出里加一列「子集来源」（由哪个子集经过哪个字母得到），报告里写清楚每个子集的来历，答辩时被追问也答得上。

5.4 多初态 NFA 结果少了一半

现象：NFA 声明了两个初态，子集构造跑出来的第一个子集只包含其中一个初态的闭包，另一个初态及其后续状态完全没出现在结果里。

原因：新增初态 X 只连了一条 ε 弧到「非空初态集里的某一个状态」。这是原文明确写下的简化，「连到任意一个太麻烦」。单初态时看不出问题，多初态时剩下那几个初态的闭包根本进不了第一个子集，整棵可达树被砍掉一半。

解决：X 到每个初态都连 ε 弧，或者干脆不插 X，直接求epsilonClosure(nfa, nfa.starts)。后者更省事，语义完全等价。终态同理，用「子集与终态集有交集」判断，不要只认 Y 一条弧。

5.5 charAt 固定下标解析在换格式后全线崩

现象：把状态名从1、2改成q1、q2，程序要么抛StringIndexOutOfBoundsException，要么算出一堆不存在的状态。

原因：charAt(1)、charAt(3)、charAt(6)这三个下标是照着(1,a)→3这个模板数出来的，隐含「括号一位、状态一位、箭头两位」的假设。状态名变两位，第三个字符就不是字母了；逗号后面多一个空格，所有下标整体偏移。

解决：坚决不用固定下标解析结构化文本。用split按分隔符切，或者正则可选分组，把「格式」和「取值」分开。第 2 章的逗号分隔格式就是为这个改的。如果必须兼容原有(1,a)→3写法，至少用replaceAll("[()→\\s]", "")先清一遍外壳再切，别数下标。

// 兼容旧格式：(1,a)→3 或 ( q1 , a ) → q2 static Transition parseLegacy(String line) { String core = line.replaceAll("[()\\s→]", ""); // 去掉括号、箭头、空白 String[] p = core.split(","); if (p.length != 3) throw new IllegalArgumentException("无法解析转移：" + line); return new Transition(p[0], p[1], p[2]); }

replaceAll里→直接写在字符类里，不需要转义。这行代码比三个charAt多敲了几个字符，换来的是状态名随便改都不会崩。

6. 验证闭包对不对：手算对照、位集加速与一个可复用的检查习惯

闭包这种东西，光看代码看不出对错，必须有一组能手工核对的小用例。我一般固定跑三个：单状态无 ε 出口（闭包等于自身，验证恒等性）、三层 ε 链（验证递归深度）、两个状态互为 ε 环（验证去重和终止）。这三个过了，再上真实数据。

完整对照建议用报告里的那个例子，手算一遍贴表里比：

手算的关键不是算得多快，是每一步都写清楚「这个状态是从哪条弧进来的」。只要有一格对不上，顺着那条弧往回查，比对着输出瞎猜快十倍。

规模上去之后，Set<String>的开销会变成瓶颈。常见做法是把状态编号映射成整数，用java.util.BitSet表示集合，闭包运算就是按位或：

/** 预先把 ε 弧的闭包算好存在一张表里，运行期只做按位或 */ static BitSet[] precomputeEpsilon(Nfa nfa, Map<String, Integer> idOf) { BitSet[] table = new BitSet[nfa.states.size()]; for (String s : nfa.states) { int id = idOf.get(s); BitSet bs = new BitSet(); for (String t : epsilonClosure(nfa, List.of(s))) bs.set(idOf.get(t)); table[id] = bs; } return table; }

预计算的开销是 O(n × 闭包大小)，换来的是运行期每次求闭包只需对若干个BitSet做or，比反复建HashSet快一个量级，也让「两个子集是否相同」退化成BitSet.equals。代价是状态必须提前编号，输入里出现新状态就得重建映射表。课设规模下不必上这套，但知道有这么一条路，遇到状态数上百的自动机时不会手足无措。

最后说一个习惯。我在写这类「递归 + 收集结果」的代码时，只要发现返回值没被接住，就会立刻停下来改结构，不管当前测试是不是碰巧能过——因为这类 bug 的表现完全取决于输入数据的形状，测不到不代表不存在。从那以后我每次改完闭包函数，都强制走一遍那三个最小用例再跑完整例子，宁可多花五分钟，也不愿意在报告交上去之后才发现某个 ε 环把结果带偏了。希望帮到你。

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