同一正则语言是否存在多个最小DFA？最小DFA状态数是否必相等？

1. 是否可能针对同一正则语言构造出多个最小DFA？ #

可以构造出多个形式上不同的最小DFA，但它们状态数一定相同，且本质是同构的——只是状态的命名、编号不同，或者转移的表述形式有差异，核心的状态等价类划分和转移逻辑完全一致。

2. 等价DFA最小化后的状态数是否一定相同？ #

是的。根据DFA最小化的理论，任意正则语言对应的最小DFA在同构意义下是唯一的。也就是说，无论你从哪个等价的DFA出发进行最小化，最终得到的最小DFA状态数必然相同，只是可能存在状态命名的差异。

关于你设计的DFA问题 #

字母表{0,1}上“末尾第二位为1”的字符串构成的语言，其最小DFA确实是3状态的。你设计的4状态DFA一定存在可合并的等价状态，说明你的最小化步骤可能有误。

举个该语言的最小DFA示例：

• 状态S₀（初始状态，未读到足够长度的字符）：读0或1都转移到S₁
• 状态S₁（已读1个字符，当前末尾第一位，尚未满足末尾第二位为1）：读0转移到S₁，读1转移到S₂
• 状态S₂（接受状态，末尾第二位为1）：读0转移到S₁，读1转移到S₂

你可以重新检查4状态DFA的状态等价性，通过区分可区分状态的方法（比如从接受状态反向推导），就能合并冗余状态得到3状态的最小DFA。

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