Дизайн DFA принимает десятичные строки, делимые на 7

Question

Я студент, изучающий DFA, ищущий DFA, который мог бы найти, если десятичное число делится на 7.

Сегодня я решил проблему делимости для чисел 2,3,4,5,6, 8,9, но я не могу решить эту проблему для числа 7. Я искал в Интернете, но не смог найти ответа, который помог бы мне или был понятен для меня.

так что теперь я здесьищу помощь.заранее спасибо.

Answer 1

Основная идея состоит в том, что мы будем отслеживать текущее значение, по модулю семь, числа, которое мы видели до сих пор.Каждая новая цифра берет старое число, умножается на десять и добавляет новую цифру.Следовательно, из состояния, соответствующего x (мод 7), добавление цифры d справа означает, что мы переходим в состояние, соответствующее 10x + d (мод 7).Этот 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, состояние, соответствующее нулю по модулю семь, что означает четное число, кратное семи.