设计 DFA 接受可被 7 整除的十进制字符串

Question

我是一名学习 DFA 的学生，正在寻找一个可以查找十进制数是否能被 7 整除的 DFA。

今天我已经解决了数字 2,3,4,5,6,8,9 的整除问题，但我无法解决数字 7 的这个问题。我在网上搜索过，但找不到任何帮助我的答案或者对我来说是可以理解的。

所以现在我来这里寻求帮助。提前致谢。

Answer 1

基本思想是，我们将跟踪迄今为止所看到的数字的当前值（模七）。每个新数字都将旧数字乘以十，然后加上新数字。因此，从 x (mod 7) 对应的状态，向右添加数字 d 意味着我们进入 10x + d (mod 7) 对应的状态。这个DFA有70种状态（0-9的位数乘以7个0-6后的余数）。

\n\n

q    s    q'\n------------\nq0   0    q0\nq0   1    q1\nq0   \xe2\x80\xa6    \xe2\x80\xa6\nq0   6    q6\n\nq1   0    q3\nq1   1    q4\nq1   \xe2\x80\xa6    \xe2\x80\xa6\nq1   6    q2\n\n\xe2\x80\xa6\n\nq6   0    q4\nq6   1    q5\nq6   \xe2\x80\xa6    \xe2\x80\xa6\nq6   6    q3\n

\n\n

考虑数字 36736 的处理：

\n\n

(q0) --3--> (q3) --6--> (q1) --7--> (q3) --3--> (q5) --6--> (q0)\n0           0*10+3      3*10+6      1*10+7      3*10+3      5*10+6\n            0+3         30+6        10+7        30+3        50+6\n            3           36          17          33          56\n            3           1           3           5           0\n

\n\n

这个数字可以被七整除，因为我们最终处于状态 q0，该状态对应于零模七——意味着七的偶数倍。

\n