构造最小化DFA：{a,b}上子串"aba"出现次数≡2(mod3)的字符串集合

一、原始DFA构造 #

状态定义 #

我们需要同时跟踪两个核心信息：

• 匹配进度：标记当前对目标子串"aba"的匹配阶段：
  • S0：未匹配"aba"的任何前缀
  • S1：已匹配前缀"a"
  • S2：已匹配前缀"ab"
  • S3：刚完成一次完整的"aba"匹配
• 计数余数：当前"aba"出现次数除以3的余数，取值为0,1,2

因此，原始DFA的状态表示为(Sq, r)，共12个状态。其中初始状态为(S0, 0)（初始时"aba"出现次数为0，余数0），接受状态为所有余数r=2的状态：(S0,2), (S1,2), (S2,2), (S3,2)。

状态转移表 #

二、最小化DFA构造 #

通过等价类划分法完成DFA最小化：

步骤1：初始划分 #

将所有状态分为两类：

• 接受状态集F：{(S0,2), (S1,2), (S2,2), (S3,2)}
• 非接受状态集¬F：{(S0,0), (S0,1), (S1,0), (S1,1), (S2,0), (S2,1), (S3,0), (S3,1)}

步骤2：迭代细分等价类 #

反复检查每个组内的状态：若两个状态对任意输入的转移目标属于不同组，则拆分该组，直到无法再细分。最终得到的等价类及简化命名如下：

• A: {(S0,0)}（初始状态，余数0，未匹配任何前缀）
• B: {(S1,0), (S3,0)}（余数0，匹配到"a"或刚完成一次"aba"匹配后回到"a"状态）
• C: {(S2,0)}（余数0，匹配到"ab"）
• D: {(S0,1)}（余数1，未匹配任何前缀）
• E: {(S1,1)}（余数1，匹配到"a"）
• F: {(S2,1)}（余数1，匹配到"ab"）
• G: {(S3,1)}（余数1，刚完成一次"aba"匹配）
• H: {(S0,2)}（接受状态，余数2，未匹配任何前缀）
• I: {(S1,2), (S3,2)}（接受状态，余数2，匹配到"a"或刚完成一次"aba"匹配后回到"a"状态）
• J: {(S2,2)}（接受状态，余数2，匹配到"ab"）

最小化DFA的状态转移表 #

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