Конечные автоматы, которые принимают двоичные строки, делимые на n

Я работаю над набором задач для класса и подумал над вопросом, касающимся того, над чем я работал. Существует ли минимальное количество состояний, которое должен иметь конечный автомат, чтобы принимать двоичные строки, представляющие числа, кратные целому числу n? В более раннем наборе задач я смог построить DFA, который принимал двоичные строки, делимые на 3 с 3 состояниями. Это совпадение, или есть что-то присущее общей задаче обнаружения строк, делимых на n, что предполагает минимальное количество состояний?

Я обещаю, что это не ответит на домашнее задание для меня! :)

Для такого конечного автомата известна формула минимального числа состояний. Это зависит как от так и от радиуса R базового позиционного представления.$n$$R$

Если взаимно просто с R , то минимальное число состояний равно n . Однако, когда n делит коэффициент с основанием, тогда ситуация довольно сложная. См. Mathematica Journal Vol. 3 Issue 11. «Делимость и сложность состояния» Клауса Сатнера.$n$$R$$n$$n$

Есть еще одна статья на эту тему: Б. Алексеев, Минимальный DFA для проверки делимости, J. Comput. Сист. Sci. 69 (2004), 235–243.