如何证明该DFA（确定有限自动机）是对应并运算的最小自动机？

要证明一个DFA是对应场景的最小自动机，只需验证两个核心条件全部满足即可：

• 所有状态均为初始状态可达状态：所有状态都能找到从初始状态出发的转移路径，不存在无法到达的孤立状态。
• 任意两个不同状态均可区分：不存在等价状态，即对任意两个不同的状态，总能找到至少一个输入串，使得两个状态处理该串后，一个进入接受状态、另一个进入非接受状态。

验证可区分性最常用的方法是填表法，操作流程如下：

1. 列出所有两两配对的状态对，首先把「一个是接受态、另一个是非接受态」的状态对直接标记为可区分
2. 遍历所有未标记的状态对(q₁, q₂)，对每个输入字母a，检查转移后的状态对δ(q₁,a)和δ(q₂,a)是否已被标记为可区分，如果是则(q₁,q₂)也标记为可区分
3. 重复迭代第二步，直到没有新的状态对可以被标记
4. 最终如果所有状态对都被标记为可区分，说明该DFA没有等价状态，满足最小化要求。

如果是针对并运算构造的乘积DFA，额外确认乘积构造的状态定义符合并运算的接受规则即可，不需要额外合并状态就符合要求。你上传的推导如果已经完成了上述两个条件的验证，结论就是正确的。

内容的提问来源于stack exchange，提问作者CS_student