简介这是一份面向计算机专业学生的编译原理课程设计报告围绕Java实现有限自动机NFA空闭包ε-closure(I)计算展开解决输入任意NFA后输出指定状态子集空闭包、并自动绘制状态转换图的问题。资源为1个docx文档约177KB内含完整报告正文与程序源代码附录可直接参照或扩展。已有1284人学习适合需要完成同类课程设计、实验作业或复习自动机理论的读者。报告从需求分析、概要设计到详细设计逐步拆解重点阐述了数组、哈希表、状态转移函数以及递归求空闭包的实现思路并针对新初态X与终态Y的引入、读字母表函数等难点给出具体处理方案。实现过程中使用静态变量累积递归中间结果先求X的空闭包再对子集读字母和空弧循环扩展最终输出全部状态子集。测试部分包含多组NFA输入与运行结果用户使用说明能帮助快速上手。代码附录可作基础框架复用为理解ε-closure概念及编译原理实践提供扎实参考。1. 一个容易被当成“小工具”的闭包计算能毁掉整张DFA表编译原理课程设计里ε-closureI是第一炮给定一个NFA状态集合I求所有只靠ε边就能到达的状态并成一个新集合。很多同学把它当成半小时能写完的附带工具结果做子集构造法生成DFA表时每个状态集都差一两个元素整张表全对不上。这一题本身不难却是NFA转DFA流水线的入口承接了后续转移表构造和状态最小化任何一步理解偏差都会以“玄学bug”的形式在后面冒出来。这篇笔记按课程设计报告的拆法把原理、Java实现、验证和踩坑一次讲完适合正在写这套实验报告、或者打算用Java完整走一遍编译预处理流程的读者。2. ε-closureI到底是什么从NFA的不确定性到状态集合的封闭空间2.1 ε边和闭包一个“不加字符也能走”的状态汇聚规则NFA与DFA的根本区别在于一个状态读到一个字符后可能跳向多个后继状态而这多个后继里还混着一类特殊转移——ε转移。它不消耗任何输入字符纯粹表示一种“自动切换”能力等价于当前状态可以在不做任何输入的情况下变成另一个状态。这种设计让正规式转NFA变得很自然但也带来一个麻烦某个时刻NFA可能同时处于多个状态而DFA的每个状态必须能明确回答“我到底在哪”。ε-closure(I)把这一团乱麻先收拢一遍。它的定义是从集合I中任意一个状态出发沿ε边走任意步包括0步能到达的全部状态的集合。注意“任意步”是闭包这个称呼的来源也意味着闭包必须包含I里的所有状态本身因为走0步也算。用一个例子立刻能看明白状态1有一条ε边指向状态2状态2又有一条ε边指向状态3那么ε-closure({1}) {1, 2, 3}。不算上1和3闭包就不完整这是新手最容易犯的第一个错。为什么要先算闭包再转DFA因为DFA不允许“什么都不读就换状态”。ε边是NFA特有的不确定性来源如果不预先吸收掉后面子集构造法每算一步都得反复追ε路径逻辑会乱成一团。闭包计算相当于把NFA里所有“隐藏的瞬移路径”一次性展开之后每次按输入字符跳转时看到的都是干净的状态集合。这也是为什么几乎所有编译原理教材都把ε-closure放在NFA转DFA章节的最前面。2.2 标题里的I是什么它不是一个序号而是闭包的自变量很多同学拿到课程设计题目“ε-closureI的程序实现”会误以为I表示第一阶段、第二部分其实这里的I是数学记号里的状态子集通常用大写斜体I表示“初始状态集合”或“某一组状态”。教材里标准的写法就是ε-closure(I)其中I ⊆ SS是NFA全部状态的集合。闭包运算的输入是一个集合输出也是一个集合这种“集合到集合”的映射正是整个子集构造法的基本操作单元。既然输入是集合那单个状态的闭包就只是一个特例ε-closure({s})。课程设计里往往第一步要求实现单个状态的闭包因为打印输出直观、便于和教材例题对答案第二步再要求实现对集合I的整体闭包。两者在算法上完全一样因为闭包运算有一个关键性质对集合的闭包等于对集合内每个状态分别求闭包再取并集。用公式表达就是ε-closure(I) ∪ ε-closure({s})s ∈ I。这个性质保证了我们可以直接对传入的集合做一次BFS不需要先逐个状态算完再合并。这个性质也解释了为什么闭包结果自带“封闭性”对闭包结果再求一次闭包得到的是同一个集合。代码里不需要反复调用直到不动点一趟BFS天然保证了这一点。写课程设计报告时如果把这条性质写进设计说明里并附上一个“closure(closure(I)) closure(I)”的断言测试整个报告的完整度会明显提升后面做DFA表时也不用担心闭包结果被重复迭代污染。2.3 用邻接表还是邻接矩阵Java实现里的第一道选择题闭包计算本质上是图遍历。NFA的状态数量在课程设计场景下通常只有十几个到几十个两种存法都跑得动但选型会影响代码可读性。邻接矩阵用boolean[n][n]存ε转移矩阵[c][t]为true表示状态c能通过ε一步到t。优点是下标访问直观缺点是ε边在真实NFA里非常稀疏矩阵大部分是false遍历一个状态的后继时得扫一整行白做很多次判断。我一般会用邻接表具体结构是MapInteger, Set key是源状态编号value是它通过ε边一步能到达的所有状态编号集合。闭包算法里最频繁的操作是“给定当前状态找出所有ε后继”邻接表正好把这个操作变成一次Map查找时间复杂度接近O(1)的哈希访问。如果担心Java里Set的遍历顺序不稳定影响调试可以改用LinkedHashSet或者直接用TreeSet代价是插入稍慢但打印出来的闭包结果是升序的对课程设计报告里的手工核对特别友好。另一个容易被忽略的点是状态编号。建议一律从0开始编号并让编号连续分布在0到n-1区间。这样后面无论是开boolean矩阵、数组还是做BitSet映射都不用做偏移换算。如果你的NFA来源是教材例题里面的状态可能从1或0开始画转成代码时先做一次统一编号能省掉后面所有数组越界的排查。下面第3章的数据结构就把状态编号约束在0..n-1保证闭包算法和后续子集构造法共用同一套编号体系。3. 用Java实现ε-closureI完整类结构、BFS主循环与方法参数3.1 先把NFA的ε表建模成可测试的数据结构课程设计的第一步不是写闭包方法而是先把NFA的ε转移表存进来。我会把“只负责闭包计算”的类和“描述NFA”的数据结构分开这样闭包类能独立测试不依赖具体的NFA是从文件读的还是手工构造的。下面这个类是一个最小骨架import java.util.*; public class EpsilonClosure { // 邻接表key 是当前状态编号value 是它经过一条 ε 边可一步到达的状态集合 private final MapInteger, SetInteger epsilonMoves; public EpsilonClosure(MapInteger, SetInteger epsilonMoves) { // 拷贝一份防止外部修改破坏内部结构 this.epsilonMoves new HashMap(epsilonMoves); // 补全缺失的 key让所有状态至少有“后继为空”的集合 for (int state : getAllStates(epsilonMoves)) { this.epsilonMoves.putIfAbsent(state, new HashSet()); } } }构造器里做了两件事。第一是拷贝外部传入的Map避免调用方在后面修改原表导致闭包结果不稳定这是写课程设计时一个很小但很加分的习惯。第二是把转移表里没出现的状态也补一个空集合比如某个状态只出现在别人的后继里、自己却没有出边如果不补全后面getOrDefault逻辑虽然也能处理但调试打印时会少一个条目容易看错。辅助方法getAllStates收集所有出现过的状态编号既包括作为key的源状态也包括作为后继的目标状态。这个工具方法在子集构造法里也会复用因为DFA状态集合的编号往往远大于NFA初始状态数收集全集能避免漏状态。实现上遍历一遍所有key和所有value里的元素塞进一个TreeSet再返回保证编号有序。3.2 核心方法BFS主循环每个判断都值得讲清楚闭包计算我选BFS而不是DFS原因是课程设计里随时可能冒出ε环比如状态0能经ε到状态1状态1也能经ε回到状态0。递归DFS在环上会无限递归就算加了visited标记深链路上也可能栈溢出BFS借助显式队列和HashSet兜底天然安全。下面是核心方法public SetInteger closure(SetInteger states) { // 闭包结果初始就包含传入集合本身走 0 步也算 SetInteger result new HashSet(states); // 用队列做广度优先搜索 DequeInteger queue new ArrayDeque(states); while (!queue.isEmpty()) { int current queue.poll(); // 取出当前状态的 ε 后继集合没有后继就取空集 SetInteger nextStates epsilonMoves.getOrDefault(current, Set.of()); for (int next : nextStates) { // add 返回 true 说明 next 是第一次进 result需要继续扩展 if (result.add(next)) { queue.add(next); } } } return result; }这个方法的正确性建立在两个细节上。第一result初始就copy传入的states保证“走0步也算”的语义有人会把初始状态也先塞进队列然后等出队时才往result里加这样会漏掉没有ε后继的孤立状态比如closure({5})如果5没有任何出边队列一弹出来就结束result里根本没有5。我习惯初始化时直接加队列也直接拿states做种子两边同步语义最干净。第二result.add(next)同时充当了“去重”和“是否入队”的判断。Java里Set.add在元素已存在时返回false因此只有当next是第一次被发现时才入队这样每个状态最多入队一次时间复杂度是O(VE)V是状态数E是ε边总数。如果不用这个返回值改成先contains再add再入队结果一样但会多做一次哈希查找还容易在并发改动时出问题。这里取getOrDefault的空集是Set.of()它是一个不可变空集合只用于遍历所以安全。3.3 集合闭包与单状态闭包的一致性为什么传整个I进来是最高效的前面提到ε-closure(I)可以拆成对每个状态分别求闭包再合并那为什么还要写一个接收集合的版本直接遍历集合里的每个状态调closure({s})再union代码也能跑但会产生一个问题不同的状态子集共享大量ε路径逐个算等于把同一段图反复走好几遍。比如I {0, 3}0和3的ε路径都汇合到状态10分开算时状态10会被访问两次合在一起BFS状态10只在第一次被发现时入队一次。数据规模小看不出差别但课程设计的NFA如果来自正规式合并路径汇合点非常多合算的耗时能差出好几倍。我们还能从另一个方向验证这个实现没写歪。因为闭包是幂等的closure(closure(I))应该等于closure(I)。把这个断言写进测试比对着教材例题手算更能抓住“闭包集合被外部修改”“队列初始化漏了状态”这类隐蔽问题。我在实际项目里还会把这个性质封装成一个静态方法public SetInteger closureAndCheckSelf(SetInteger states) { SetInteger first closure(states); SetInteger second closure(first); if (!first.equals(second)) { throw new IllegalStateException(closure 结果不满足幂等性epsilon 表有改动); } return first; }这个方法在调试阶段很有用。如果NFA的构造代码里存在修改ε表的逻辑闭包结果会不稳定幂等检查能第一时间让程序报错而不是让后续DFA表生成出一堆莫名其妙的状态。正式交付时可以把这层检查去掉毕竟每多一次遍历就多一点开销但报告里提一句“实现时用幂等性断言验证过数据完整性”是能加分的工程细节。3.4 一个能直接跑通的最小例子3状态链式ε转移为了验证上面的类没写错我会搭一个最小的链式NFA状态0有一条ε边到状态1状态1有一条ε边到状态2状态2没有出边。手动算一下ε-closure({0}) {0, 1, 2}。对应的Java初始化代码长这样public static void main(String[] args) { MapInteger, SetInteger moves new HashMap(); moves.put(0, new HashSet(Set.of(1))); moves.put(1, new HashSet(Set.of(2))); moves.put(2, new HashSet()); EpsilonClosure ec new EpsilonClosure(moves); System.out.println(ec.closure(Set.of(0))); // 期望输出 [0, 1, 2] System.out.println(ec.closure(Set.of(1))); // 期望输出 [1, 2] System.out.println(ec.closure(Set.of(0, 1))); // 期望输出 [0, 1, 2] }三个打印结果能覆盖主要语义。第一个验证链式传递第二个验证闭包不包含前面绕过的状态第三个验证集合输入的合并逻辑。运行这个main之前要注意Set.of是Java 9才有的API课程设计的JDK环境如果还在8就得改成new HashSet(Arrays.asList(1))。另外moves.get(2)放一个空的HashSet是必要的因为构造器里虽然有补全逻辑但这里显式写出更容易对照转移表。如果看到输出是[0, 1, 2]说明闭包基本逻辑通了。但这只能证明一条链没算错还证明不了带环、带分支的情况正确。下一章给出两类更有说服力的测试一类是手算程序对拍的针对用例另一类是固定种子的随机NFA属性测试后者能把“玄学通过”变成“结构化验证”。4. 怎么验证闭包算得对教材例题对照与固定种子的随机NFA测试4.1 手算对照搭一个3状态串行ε链课程设计报告里最好有一张手工推导表评审老师一眼就能看出你是否真的理解闭包过程。拿上面那条链来说完整推导是从0出发0自身计入沿ε到达11计入从1沿ε到达22计入2无出边结束。表驱动写法可以做成下面这样的两列对照左边是待扩展状态右边是新增闭包成员当前状态沿ε新加入的状态本轮后闭包集合01{0, 1}12{0, 1, 2}2无{0, 1, 2}这张表对应的程序输出就是上一章main方法里的第一行。写报告时把这张表和代码截图并排放比单独贴一段代码更有说服力。注意表格里“本轮后闭包集合”列用的是有序集合显示如果程序里用的是HashSet遍历顺序可能不固定建议打印前先转成TreeSet或者直接用LinkedHashSet初始化结果集合避免每次运行截图长得不一样。4.2 加入ε环测试BFS不会死循环的关键用例链式NFA只能验证闭包的传递性验证不了环。环才是BFS和DFS真正的分水岭。设计一个三状态环状态0能经ε到1状态1能经ε到0和2状态2没有出边。ε-closure({0})的结果还是{0, 1, 2}但如果算法写成无脑递归且不做访问标记这段代码会无限在0和1之间循环直到栈溢出。状态 0: ε - 1 状态 1: ε - 0, 2 状态 2: ε - 无用这个表驱动测试时我建议在main里加一个计数器或者直接观察程序是否能在100毫秒内结束。真正可靠的验证还是看闭包集合是不是三个状态且不重复。这里的特殊之处在于从0出发访问1后1的后继里有0此时result.add(0)返回false所以0不会再入队环被自然截断。把这条用例和链式用例都写进JUnit测试里比单独跑main更可回归。4.3 固定种子随机NFA用性质断言替代人工核对手算用例再多也没法保证覆盖所有图形结构。我惯用的做法是写一个随机NFA生成器固定随机种子然后针对闭包运算的数学性质做断言。这样做的好处是每次失败都能稳定复现不会出现“昨天过今天挂”的随机性玄学。下面这段代码用固定种子生成一个有20个状态的随机ε图import java.util.*; public class ClosureRandomTest { public static void main(String[] args) { Random random new Random(20240601L); // 固定种子失败可复现 for (int round 0; round 100; round) { MapInteger, SetInteger moves new HashMap(); for (int s 0; s 20; s) { SetInteger targets new HashSet(); // 每个状态最多加 3 条 ε 出边目标也是随机状态 int edgeCount random.nextInt(4); for (int e 0; e edgeCount; e) { targets.add(random.nextInt(20)); } moves.put(s, targets); } EpsilonClosure ec new EpsilonClosure(moves); // 随机挑一个子集作为 I子集大小也在 0 到 5 之间浮动 SetInteger input new HashSet(); int inputSize random.nextInt(6); for (int i 0; i inputSize; i) { input.add(random.nextInt(20)); } SetInteger first ec.closure(input); SetInteger second ec.closure(first); // 性质1闭包必须包含输入集合本身 if (!first.containsAll(input)) { throw new AssertionError(闭包丢失输入状态); } // 性质2闭包是幂等的二次闭包等于一次闭包 if (!first.equals(second)) { throw new AssertionError(闭包不满足幂等性); } // 性质3空集合的闭包仍是空集合 if (input.isEmpty() !first.isEmpty()) { throw new AssertionError(空集合闭包非空); } } System.out.println(随机测试通过); } }三条断言分别对应闭包运算最核心的三个性质。闭包包含自身是定义要求幂等性代表“闭包已经收拢完毕”不满足就意味着算法漏了某些路径空集闭包为空是边界条件很多实现在队列用null优化时会翻车。这里的随机图每次生成100轮每轮20个状态总量不大但能覆盖环、多分支、孤立状态等结构。如果随机测试跑挂了第一步先看是哪个轮次挂的把这一轮的moves和input打印出来。固定种子的价值就在这里同一台机器上重跑生成的图和输入一定相同你可以把那组数据直接抽出来做最小化复现。如果嫌循环里打印太吵可以只在失败分支里打印成功时保持安静。4.4 和教材例题的最终对拍别只盯着自己的图随机测试能证明算法在任意结构上不出错但证明不了“你的输入转移表描述对了”。课程设计里最常见的错误其实发生在NFA表达阶段把教材里的状态图抄成转移表时抄错一条边闭包算法再正确也算不出预期结果。所以在交付前一定要找一道教材例题做端到端对拍。编译原理清华大学出版社第三版第二章里有一批“正规式转NFA”的练习里面大量涉及ε边。挑一道带多个ε分支的题手工构造它的ε转移表然后手动写一遍闭包结果再用程序跑一遍两者必须一致。如果你手头教材的习题答案不好查可以选一个自己确定能推导的简单正规式比如(a|b)*abb转NFA它的NFA里既有ε分支又有汇合闭包结果需要算好几轮足够暴露大多数实现问题。这类用例建议单独放在一个测试类里不要混进随机测试因为它是固定的、有业务含义的将来写报告时可以直接贴出对拍数据。5. 避坑ε-closureI实现里最常见的5个翻车点5.1 闭包结果漏掉自身状态静态检查根本看不出来现象链式用例closure({0})输出为{1, 2}少了0。凡是输入状态没有出边的情况输出直接变成空集。排查时第一眼会觉得是队列初始化问题实际上是把“走0步也算闭包”的语义漏了。原因很统一有人先建空result然后从输入状态出发入队在出队时才把当前状态加入result。这个逻辑漏掉了“状态自身没有出边但必须计入闭包”的情况。解决把result初始化为new HashSet(states)队列也用states做初始种子两者同步。我见过另一种修法是在循环结束后把states再add一次也能过测试但语义上没第一种清晰。写代码时在方法上方加一行注释“包含输入集合本身”能防止以后改代码时再次踩掉。这个坑的隐蔽性在于只要NFA里每个输入状态都至少有一条ε出边漏自身状态就不会暴露等遇到孤立状态才突然翻车。5.2 用递归DFS实现闭包在ε环上栈溢出现象程序在小NFA上跑得好好的换一个带ε回边的NFA运行时报StackOverflowError而且报错栈反复指向同一个状态。原因递归DFS天然支不支持环检测即使外层有visited集合递归深度仍可能随着ε路径长度线性增长如果A到B、B到A相互可达不去重就会无限递归去重逻辑写得不对也只是从“必挂”变成“看路径长度看运气”。解决直接用BFS加显式队列闭包深度和递归栈彻底解耦。BFS的代码量并不比DFS多而且队列长度上限就是状态总数内存占用完全可控。如果课程设计里有人坚持用DFS那至少要在递归入口处先查visited再进入下一层但我不推荐给结论闭包这种“必须遍历全部可达集”的场景BFS就是最稳的答案。考试笔算时DFS方便代码实现选BFS不冲突。5.3 状态集合用ArrayList存放重复状态悄悄撑爆DFA表现象闭包结果偶尔看起来是对的但后面做子集构造法时DFA状态数量异常膨胀几百个状态都停不下来。原因闭包返回的是List每次往列表尾部追加新状态前没有去重导致同一个状态在集合里出现多份。闭包算法里用list.contains去重不是不行但它是O(n)的状态一多整个算法退化到O(n^3)。解决闭包结果一律用Set语义。HashSet适合做过程容器LinkedHashSet适合做输出容器TreeSet适合做需要打印升序结果的场合。我个人的习惯是方法内部用HashSet做添加逻辑最后返回前如果外部要打印在外层转成TreeSet。这不算过度设计因为子集构造法里一个DFA状态就是一组NFA状态集合这个集合必须无重复、无顺序依赖否则两个内容相同但添加顺序不同的集合会被当成不同DFA状态接下来就是状态爆炸。5.4 状态编号从1开始导致后继数组越界现象NFA图里有编号10的状态后继集合里却出现IndexOutOfBoundsException或者数组大小够却一直越界。原因很多教材和PPT画NFA时从1编号实现时有人直接用数组下标当状态号数组开成int[states.size()1]却忘了某些中间状态下标可能超过这个值。如果再加一个状态出来越界问题立刻浮现。解决从实现的第一行就规定状态编号必须连续且从0开始。如果NFA数据里状态编号是1到n读入时统一减一如果状态编号还有不连续的情况比如0、1、5、7先做一次映射表把旧编号拍平成0、1、2、3。这个映射表在输出报告时还能反过来把DFA状态编号映射回NFA原始编号方便人工核对转移表。不要迷信数组开大一点就能解决数组只是编码手段编号连续性不够照样会错。5.5 闭包结果不缓存子集构造法重复计算到失控现象NFA只有十几个状态但整个NFA转DFA程序跑了几十秒还没结束CPU跑满但内存不高。原因子集构造法里每隔新DFA状态都要算ε-closure而新状态集合经常与旧集合大量重合。如果每个集合都从零开始遍历ε表总计算量随DFA状态数平方增长教育场景里NFA小可能还能忍状态一多就原形毕露。解决在闭包类里加一个记忆化Map以输入状态集合为key闭包结果为value。Java里Set可以作为Map的keyHashSet的hashCode已经考虑了所有元素所以相同内容的状态集合能命中同一个缓存项。加缓存时注意一个边界输入集合是可变的外部修改了集合内容后哈希值会变所以要么在调用处传不可变视图要么在get之前先做一次防御性拷贝。我自己的做法是缓存key用new HashSet(states)复制一份虽然多花一点内存但能彻底避开集合可变性这个坑。6. 让I服务整套实验把闭包接进子集构造法报告里再多写五步6.1 子集构造法主循环里闭包被调用的两个位置闭包计算本身不是终点它要配合move操作才能生成DFA。move(T, a)的定义是从T中任一状态出发读一个字符a能到达的所有状态集合注意这个结果通常不含ε后继。所以子集构造法里每生成一个新DFA状态都要先算“读字符后的move结果”再对这个结果求闭包二者缺一不可。加进缓存后的调用长这样public SetInteger closureCached(SetInteger states) { return cache.computeIfAbsent(new HashSet(states), this::closure); } public SetInteger move(SetInteger states, char symbol) { // NFA 的字符转移表由外部传入这里只做集合展开 SetInteger target new HashSet(); for (int s : states) { SetInteger next charMoves.getOrDefault(s, Map.of()) .getOrDefault(symbol, Set.of()); target.addAll(next); } return target; }closureCached负责把闭包结果缓存起来move负责收集字符跳转。两者组合起来就是DFA其中一个转移的完整计算。写报告时建议把“对move后的集合立刻求闭包”作为一个独立小节配一张三步走的表原始状态集合T、经过字符a的move结果、再闭包后的最终DFA状态。这张表能清楚展示闭包在流水线里到底卡在哪个环节比单纯描述算法更有说服力。6.2 做完这一步后面的实验能复用哪些成果如果课程设计还有下一部分比如DFA最小化闭包代码能直接复用的成果主要有两个一是“状态集合”的哈希实现DFA状态去重完全依赖它二是缓存表里已经生成的闭包结果最小化时不涉及ε边但DFA状态编号的映射表可以直接拿来用。我做完这道题后养成的一个习惯是闭包结果一律先转成升序字符串打印一遍和手算表逐行核对再进主流程。这个过程多花一分钟但能省掉后面排错一小时。希望帮到你。本文还有配套的精品资源点击获取