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

Question

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

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

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

Answer 1

基本思路是，我们将跟踪我们目前看到的数字的当前值，modulo 7。每个新数字都取旧数字乘以 10，然后加上新数字。因此，从x(mod7)对应的状态，向右加上d位，就是10x+d(mod7)对应的状态。这个DFA有70个状态（位数0-9乘以七除后的余数0-6）。

q    s    q'
------------
q0   0    q0
q0   1    q1
q0   …    …
q0   6    q6

q1   0    q3
q1   1    q4
q1   …    …
q1   6    q2

…

q6   0    q4
q6   1    q5
q6   …    …
q6   6    q3

考虑号码36736的处理：

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

这个数字可以被七整除，因为我们最终进入状态 q0，该状态对应于零 modulo 七 - 意思是七的偶数倍。

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

Design DFA accepting decimal strings divisible by 7

automata

finite-automata

dfa