This paper presents a solution to the question of the size fb(k) of the minimal deterministic finite automaton (DFA) accepting the strings in base b that denote integers divisible by k.
The author presents interesting numerical data in terms of the function &lgr; (x,y) = , from which a closed form for fb(k) is derived. The proof of the construction of the minimal DFA states is in terms of a back-and-forth correspondence, using standard automaton theory concepts, especially the Myhill-Nerode Theorem, between the lexical structure and the arithmetic denotation of strings.
The paper offers a clean (even exuberant!) exposition of the result. Perhaps the author might have mentioned Cobham’s theorem [1] in establishing the context of interest for this kind of arithmetic-combinatorial automaton problem.
