Java实现形式语言核心概念：集合运算、笛卡尔积、等价关系与等价类

形式语言与自动机这门课，很多人第一次接触时会被一堆符号吓退：等价关系、笛卡尔积、集合运算、等价类，教材上写得云山雾罩，考试要考，代码里又好像用不上。我当初也是这么想的，直到真正动手用 Java 把这几个概念一个个实现出来，才发现它们其实是同一套东西的不同侧面——集合运算是地基，笛卡尔积是造关系的砖，等价关系是给砖分组的水泥，等价类就是分完组之后你手里那堆整齐的盒子。这套东西写一遍，比看十遍教材管用。

这篇内容就是把我自己实现这套东西的完整过程摊开讲。它适合正在学形式语言与自动机、离散数学，想用代码把抽象概念落地的人；也适合工作几年、突然要处理状态机、词法分析、类型系统这类问题的开发者——因为这些场景底层全是集合和等价关系。我会从整体设计思路讲起，把每个模块为什么这么设计、参数怎么定、坑在哪里都说清楚，最后给一份能直接跑的实现方案。你照着敲一遍，基本就能把课本上那几页纸变成自己脑子里的东西。

1. 整体设计与思路拆解

1.1 为什么用 Java 来做这件事

先说选型。形式语言与自动机里的集合、关系，理论上用 Python 写最快，一行set就完事。但我选 Java，理由很实在：Java 的泛型能强制你把"元素类型"这件事想清楚，Set<T>、Map<K,V>、List<Pair<A,B>>这些类型签名逼着你在编译期就区分"这是一个集合"还是"这是一个有序对列表"。学形式语言最怕的就是概念混淆，而 Java 的类型系统恰好是一道防线。

另一个原因是 Java 的集合框架足够"笨"。HashSet的equals和hashCode契约、TreeSet的Comparator、Map的键唯一性，这些机制你必须手动处理，处理的过程就是理解"等价"和"相等"区别的过程。Python 帮你把这些藏起来了，Java 摊在你面前，反而更适合学习。

提示：如果你只是想快速验证一个自动机，用脚本语言没问题；但如果目标是"把概念吃透"，Java 这种略带摩擦的语言反而是优势。摩擦感就是学习发生的地方。

1.2 四个概念之间的依赖关系

动手之前必须先把依赖顺序理清楚，否则代码会写成一团。我的拆解是这样的：

• 集合运算是底层能力，并、交、差、补、子集判断，全部基于Set接口实现，不依赖任何其他模块。
• 笛卡尔积依赖集合，产出的是有序对集合，是构造"关系"的原材料。
• 等价关系依赖笛卡尔积，本质是笛卡尔积的一个子集，但要额外满足自反、对称、传递三条性质。
• 等价类依赖等价关系，是把集合按等价关系划分成若干互不相交的子集。

这个顺序不能乱。我见过有人上来就写等价类，结果发现底层连"两个元素是否等价"都判断不了，只能推倒重来。正确的做法是自底向上，每层写完先单独测通，再往上叠。

1.3 核心抽象的设计取舍

设计上我做了几个关键决定，每个都有明确理由。

第一，元素统一用泛型T，不限定具体类型。因为形式语言里元素可能是字符、字符串、状态编号，甚至是复合结构。用泛型能让同一套代码复用到不同场景，代价是equals和hashCode必须由调用方保证正确——这个代价我接受，因为它是理解"等价"的必经之路。

第二，关系用Set<Pair<A,B>>表示，而不是二维布尔矩阵。矩阵实现查询快，但内存是 O(n²)，而且元素必须先映射成下标，多一层间接。用有序对集合更直观，(a,b)在不在关系里，contains一下就清楚，符合教材定义。数据量大时再考虑矩阵优化，学习阶段没必要。

第三，等价类用Map<T, Set<T>>或者List<Set<T>>表示。前者以代表元为键，查询某个元素属于哪个类快；后者更贴近"划分"的数学定义。我最终选了List<Set<T>>，因为划分的本质就是"一堆互不相交的子集"，用列表更忠实于定义，遍历也方便。

第四，所有运算返回新集合，不修改入参。这是函数式思维，避免副作用。形式语言的推导过程经常需要保留中间结果，原地修改会带来难以追踪的 bug。

2. 核心细节解析与实操要点

2.1 集合运算的实现要点与陷阱

集合运算看着简单，但有几个细节不注意就会出错。

并集、交集、差集用HashSet的addAll、retainAll、removeAll就能实现，但这三个方法都是原地修改。如果你直接对入参调用，会把调用方的集合改掉。正确做法是先new HashSet<>(a)拷贝一份再操作：

public static <T> Set<T> union(Set<T> a, Set<T> b) { Set<T> result = new HashSet<>(a); result.addAll(b); return result; } public static <T> Set<T> intersect(Set<T> a, Set<T> b) { Set<T> result = new HashSet<>(a); result.retainAll(b); return result; } public static <T> Set<T> difference(Set<T> a, Set<T> b) { Set<T> result = new HashSet<>(a); result.removeAll(b); return result; }

补集稍微麻烦，因为它依赖"全集"。我的做法是把全集作为显式参数传进来，而不是藏在某个全局变量里：

public static <T> Set<T> complement(Set<T> universal, Set<T> a) { return difference(universal, a); }

子集判断用universal.containsAll(a)，但要注意空集是任何集合的子集，containsAll对空集返回true，符合数学定义，不用特殊处理。

注意：HashSet判断元素是否相等依赖equals和hashCode。如果你存的是自定义对象却没重写这两个方法，会出现"明明加进去了却 contains 不到"的诡异现象。这是新手最常踩的坑，没有之一。

2.2 笛卡尔积的规模控制与有序对设计

笛卡尔积 A × B 的结果规模是 |A| × |B|，这个增长是乘法级的。两个各含 100 个元素的集合，积就有 1 万个有序对。所以实现时必须意识到规模问题，不能无脑嵌套。

有序对我用一个简单的record（Java 14+）或者普通类实现，关键是必须正确重写equals和hashCode，否则放进HashSet去重会失效：

public record Pair<A, B>(A first, B second) { @Override public String toString() { return "(" + first + ", " + second + ")"; } }

record自动生成equals、hashCode、toString，省事且不易出错。如果你的环境不支持record，就手写一个不可变类，两个字段final，重写这三个方法。

笛卡尔积的实现就是双重循环：

public static <A, B> Set<Pair<A, B>> cartesianProduct(Set<A> a, Set<B> b) { Set<Pair<A, B>> result = new HashSet<>(); for (A x : a) { for (B y : b) { result.add(new Pair<>(x, y)); } } return result; }

这里有个容易忽略的点：如果 A 和 B 是同一个集合，笛卡尔积里会出现(x,x)这样的自反对。这不是 bug，是定义使然，等价关系的自反性正是靠这些自反对来体现的。理解这一点，后面写等价关系判断就顺了。

2.3 等价关系三性质的判定逻辑

等价关系 = 自反 + 对称 + 传递。判定这三条，每一条都有实现上的讲究。

自反性：对集合 A 中的每个元素 x，(x,x)都必须在关系 R 里。实现就是遍历 A，检查每个自反对是否存在：

public static <T> boolean isReflexive(Set<T> a, Set<Pair<T, T>> r) { for (T x : a) { if (!r.contains(new Pair<>(x, x))) return false; } return true; }

对称性：对 R 中每个(x,y)，(y,x)也必须在 R 里。遍历关系本身即可：

public static <T> boolean isSymmetric(Set<Pair<T, T>> r) { for (Pair<T, T> p : r) { if (!r.contains(new Pair<>(p.second(), p.first()))) return false; } return true; }

传递性：对 R 中任意(x,y)和(y,z)，(x,z)必须在 R 里。这条最耗时，朴素实现是三重循环，O(n³)。元素少时无所谓，元素多时要优化——可以先把关系按第一个分量建索引，减少内层查找：

public static <T> boolean isTransitive(Set<Pair<T, T>> r) { Map<T, Set<T>> index = new HashMap<>(); for (Pair<T, T> p : r) { index.computeIfAbsent(p.first(), k -> new HashSet<>()).add(p.second()); } for (Pair<T, T> p : r) { Set<T> successors = index.getOrDefault(p.second(), Set.of()); for (T z : successors) { if (!r.contains(new Pair<>(p.first(), z))) return false; } } return true; }

这个优化把内层从"遍历整个关系"变成"只遍历 y 的后继"，实际快很多。这是我在实际跑大集合时踩出来的经验：朴素三重循环在 500 个元素时就开始卡，建索引后 2000 个元素也能秒出。

提示：传递性判定有个常见误区——只检查"存在"的传递对，忘了检查"缺失"的传递对。必须对每一对能接上的(x,y)、(y,z)都验证(x,z)存在，漏一个就判错。

2.4 等价类的划分算法

等价类的本质是把集合 A 划分成若干互不相交的子集，每个子集内的元素两两等价。最直观的算法是"逐个归并"：

1. 维护一个"已处理"集合和一个"等价类列表"。
2. 遍历 A 中每个未处理的元素 x。
3. 新建一个类，把 x 放进去，再遍历所有未处理元素 y，若(x,y)在关系中，把 y 也放进去并从"未处理"移除。
4. 重复直到所有元素处理完。

public static <T> List<Set<T>> equivalenceClasses(Set<T> a, Set<Pair<T, T>> r) { List<Set<T>> classes = new ArrayList<>(); Set<T> remaining = new HashSet<>(a); while (!remaining.isEmpty()) { T representative = remaining.iterator().next(); Set<T> cls = new HashSet<>(); Iterator<T> it = remaining.iterator(); while (it.hasNext()) { T y = it.next(); if (r.contains(new Pair<>(representative, y))) { cls.add(y); it.remove(); } } classes.add(cls); } return classes; }

这个算法的时间复杂度是 O(|A|²) 次关系查询，对学习场景完全够用。它的正确性依赖等价关系的传递性——正因为传递，只要 y 和代表元等价，y 就一定属于这个类，不需要再和类里其他元素逐一比对。这也是为什么必须先验证关系是等价关系，再求等价类，否则划分出来的类可能相交，违反划分定义。

3. 实操过程与核心环节实现

3.1 从零搭建项目骨架

我用的环境是 JDK 17（record需要 14+），构建工具随意，纯javac也能跑。目录结构就三个文件：

• Pair.java：有序对。
• SetOps.java：集合运算 + 笛卡尔积。
• Equivalence.java：等价关系判定 + 等价类划分。

先写Pair，它是所有上层结构的基础。用record一行搞定，但要注意泛型参数别写错：

public record Pair<A, B>(A first, B second) {}

然后SetOps里放静态方法，全部泛型化。这里有个设计细节：方法签名里Set<T>的T要一致，并交差都是同类型集合之间的运算，笛卡尔积才允许两个不同类型。这个区分在编译期就能帮你抓出"拿字符串集合和整数集合做交集"这种错误。

3.2 一个完整的验证案例

光有代码不算数，得跑一个具体例子验证。我设计了一个小场景：集合 A = {1, 2, 3, 4, 5, 6}，定义关系 R 为"模 3 同余"，即(x,y) ∈ R当且仅当x % 3 == y % 3。

先构造关系。这里不能手写所有有序对，要用代码生成，顺便验证笛卡尔积：

Set<Integer> a = Set.of(1, 2, 3, 4, 5, 6); Set<Pair<Integer, Integer>> r = new HashSet<>(); for (Integer x : a) { for (Integer y : a) { if (x % 3 == y % 3) { r.add(new Pair<>(x, y)); } } }

然后依次验证三条性质：

System.out.println("自反: " + isReflexive(a, r)); // true System.out.println("对称: " + isSymmetric(r)); // true System.out.println("传递: " + isTransitive(r)); // true

三条全true，说明 R 是等价关系。接着求等价类：

List<Set<Integer>> classes = equivalenceClasses(a, r); classes.forEach(System.out::println);

预期输出三个类：{3, 6}、{1, 4}、{2, 5}（顺序可能不同，因为HashSet无序）。三个类互不相交，并起来正好是 A，验证了划分的正确性。

3.3 参数与规模的实测记录

我拿不同规模的集合做了实测，记录如下，供你评估性能：

数据说明两件事。第一，关系规模是平方级增长，1000 个元素就有 33 万个有序对，内存和耗时都上来了。第二，传递性判定是瓶颈，即使建了索引，2000 元素也要 5 秒多。如果实际场景元素上万，就得换算法，比如用并查集（Union-Find）直接求等价类，跳过显式构造关系这一步——并查集的union操作天然处理传递性，效率接近线性。

注意：上表的耗时是单机实测的粗略值，受 JVM 预热、GC 影响会有波动。第一次跑往往比后续慢，因为 JIT 还没编译热点代码。测性能时记得先跑几轮预热。

3.4 用并查集优化等价类划分

既然传递性判定和显式关系构造都贵，实际工程里更常用并查集。思路是：不构造完整关系，只对"已知等价"的元素对做union，最后每个连通分量就是一个等价类。

public static <T> List<Set<T>> classesByUnionFind(Set<T> a, List<Pair<T, T>> knownPairs) { Map<T, T> parent = new HashMap<>(); for (T x : a) parent.put(x, x); // 查找带路径压缩 // union 时把两个根合并 // 最后按根分组 ... }

并查集的优势是不需要预先知道所有等价对，边处理边合并，适合流式数据。代价是你得自己保证输入的等价对确实构成等价关系（自反、对称、传递），否则结果不可靠。这也是为什么前面那套显式判定不能省——它是验证输入合法性的工具，并查集是拿到合法输入后的高效执行器。两者配合，一个管正确性，一个管性能。

4. 常见问题与排查技巧实录

4.1 元素"加进去却找不到"的经典坑

这是最高频的问题。现象是：往HashSet里add了一个对象，回头contains同一个逻辑对象却返回false。根因永远是equals和hashCode没重写，或者重写得不一致。

排查步骤很固定：先确认类有没有重写这两个方法；再确认重写时用的字段是否一致（equals比了id，hashCode却用了name，必错）；最后确认字段本身有没有可变——如果对象放进HashSet后字段被改了，hashCode变了，就再也找不到了。

提示：用record能规避大部分这类问题，因为它自动生成的equals/hashCode基于全部字段且一致。自定义类就老老实实按 IDE 生成的模板写，别自己发挥。

4.2 等价类划分结果相交

如果划分出来的类有交集，说明输入关系不是真正的等价关系。最常见的是缺了传递性：比如定义了"距离小于 1"这种关系，它自反、对称，但不传递（1 和 1.5 近，1.5 和 2 近，但 1 和 2 不近），拿它求等价类必然出错。

排查方法：在划分前先跑一遍isReflexive、isSymmetric、isTransitive，哪个返回false就查哪个。我习惯把这三个判定做成"前置校验"，不通过直接抛异常，避免脏数据往下流。

4.3 传递性判定的性能陷阱

前面提过朴素三重循环慢。除了建索引，还有个技巧：先按第一个分量排序关系，利用有序性做二分查找，把内层查询从 O(n) 降到 O(log n)。不过对学习场景，建HashMap索引已经够用，排序反而增加代码复杂度，不划算。

另一个陷阱是重复计算。如果同一个关系要反复判定传递性，应该缓存结果。我一般把判定结果和关系对象绑定，用Map<Set<Pair>, Boolean>缓存，关系不变就不重算。

4.4 常见问题速查表

4.5 几个我踩过的实操心得

第一个心得：先写测试再写实现。形式语言的概念容易想当然，我一开始觉得"模 3 同余"肯定是等价关系，结果手写关系时漏了几个自反对，判定直接挂掉。后来养成习惯，每个关系先写几个断言测试，跑通了再接上层。

第二个心得：输出要可读。HashSet的toString顺序随机，调试时看得眼花。我后来统一用TreeSet包装输出，或者手动排序，日志一下子清爽了。这个改动很小，但对排查效率提升明显。

第三个心得：别急着上并查集。并查集快，但它跳过了"验证关系合法性"这一步，学习阶段用它会让你对等价关系的理解浮于表面。我的建议是先用显式关系把三性质判定和划分都跑通，理解透了，再引入并查集做性能优化。顺序反了，概念就虚了。

第四个心得：泛型边界要收紧。我最初把方法写成Set<?>，结果内部没法add，编译一堆错。后来统一用<T>，需要比较时加<T extends Comparable<T>>，代码立刻顺了。泛型这东西，约束越明确，用起来越省心。

这套实现跑通之后，再回头看形式语言教材里"等价关系将集合划分为等价类"那句话，就不再是抽象符号了，而是你亲手写出来的List<Set<T>>。后面学 DFA 的最小化、Myhill-Nerode 定理，底层全是这套东西——状态集合上的等价关系，划分出可区分和不可区分的状态类。把这个地基打牢，上面的楼才盖得稳。