首字符为1且模3余1的二进制串DFA设计及校验请求

先明确要识别的语言边界 #

我们要识别的二进制串必须同时满足两个硬条件：

• 第一个字符必须是1，只要开头是0，不管后面内容是什么，直接判定为不合法。空串、单独的0字符也都不属于合法范围
• 满足起始要求的串，按二进制规则转成整数后，除以3的余数刚好是1
  • 拿题目给的示例核对：二进制1010转成十进制是10，10除以3余1，属于合法串
  • 二进制1111转成十进制是15，15除以3余0，属于非法串

推导出来的DFA正确跳转逻辑（可直接用来校验自绘图） #

因为每往串后面加一个二进制位b，新的数值就等于旧值乘2再加b，我们不需要存储完整的数值，只需要跟踪当前累计值模3的余数就行，结合开头的前置校验，整个DFA的逻辑可以拆成几块：

• 最开始的初始态只负责接收第一个输入字符：
  • 如果第一个输进来的是0，直接跳转至永久拒绝的死态，后续无论输入什么字符，都无法回到合法串的判定路径，毕竟已经违反了“以1开头”的核心要求
  • 如果第一个输进来的是1，那现在的累计值就是1，模3余1，正式进入余数跟踪的循环流程
• 三个跟踪余数的状态（分别对应累计值模3得0、1、2）的跳转必须严格符合模运算的递推关系：
  • 当前余0的时候：读0，新的余数还是0；读1，新的余数是1
  • 当前余1的时候：读0，新的余数是2；读1，新的余数是0
  • 当前余2的时候：读0，新的余数是1；读1，新的余数是2
• 能被接受的状态只有“当前累计余数是1”这一个，其他所有状态都不能作为接受态

对照检查时重点排查这几个高频设计错误 #

很多人设计这个DFA时会在几个固定环节出错，可以挨个核对：

• 有没有漏做开头校验：如果初始态不拦截前导0，直接开始计算模3余数，就会把001这种开头是0、最终值刚好模3余1的串误判为合法
• 余数跳转有没有计算错误：比如余2的时候读0，应该算出来新余数是1（因为(2*2 +0) mod 3 = 4 mod 3 =1），很多人这里会设置错跳转目标，最后整个状态机的判定结果全部错位
• 接受态有没有标注错误：别把余0或者余2的状态标成接受，不然会直接和题目给出的示例判定逻辑冲突

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