构造识别单字符语言中输入长度可被3或5整除的确定有限自动机

你的方案问题分析 #

你之前的状态设计逻辑错误在于没有利用模运算的循环特性，而是用线性递增的状态跟踪长度，导致无法正确对应“整除”的余数判断：

• 长度6应该对应模3余0的状态（即回到初始状态q0），但你的线性设计会走到q6，完全偏离了模运算的循环；
• 错误将q3、q5设为终态，但q5在你的设计里对应长度5（符合条件），但长度11（5+6）也会走到q5，而11既不能被3也不能被5整除，这是因为你的状态没有同时跟踪模3和模5的余数。

正确的DFA构造方法 #

核心思路 #

要判断长度是否被3或5整除，需要同时跟踪当前长度的模3余数和模5余数，因为“被3整除”等价于模3余0，“被5整除”等价于模5余0，只要满足其中一个条件就接受。

状态定义 #

用组合状态(a, b)表示当前状态，其中：

• a：当前字符串长度模3的余数，取值为0,1,2
• b：当前字符串长度模5的余数，取值为0,1,2,3,4
  初始状态为(0, 0)（对应空串，长度0能被3和5整除，属于终态）。

终态集合 #

所有满足a=0或b=0的状态，具体包括：

• (0,0)、(0,1)、(0,2)、(0,3)、(0,4)（长度被3整除）
• (1,0)、(2,0)（长度被5整除但不被3整除）

状态转换规则 #

对于任意状态(a, b)，输入字符x后，新状态为((a+1) mod 3, (b+1) mod 5)，举例：

• (0,0)输入x → (1,1)
• (2,4)输入x → (0,0)（长度15，同时被3和5整除）
• (0,3)输入x → (1,4)（长度4，既不被3也不被5整除）

简化版（模15状态） #

如果觉得组合状态太复杂，可以利用3和5的最小公倍数是15，用单个状态表示长度模15的余数：

• 状态为q0到q14，qk表示当前长度模15等于k
• 终态为q0、q3、q5、q6、q9、q10、q12（这些k满足k mod3=0或k mod5=0）
• 转换规则：qk输入x → q((k+1) mod15)

内容的提问来源于stack exchange，提问作者IT-Sec