# Minimal DFA that accepts binary strings whose decimal equivalent is divisible by 32

I thought the answer would be 32 for remainder $0,1,2,\dots, 31$. But answer given as $6$. and explanation is given as if the number is $2^n$ then number of states required would be $n+1$.

• Hint: what characterizes a binary string representing a number which is divisible by 32 (in decimal representation). Recall: what is 32 with respect to 2? you can try to give your own answer. – babou Feb 4 '15 at 10:46
• Actually, I think the answer may be 7, rather than 6 depending on whether you want to include 000, 0000, or 00 (for example) as a binary number representations or not. Hint: 7=5+2, or 6=1+5, and it is the 5 that is important. – babou Feb 4 '15 at 10:55
• Build any FA, determinise, minimise. What's the problem? – Raphael Feb 4 '15 at 12:04
• @Raphael Well, the first FA that came to the asker's mind has 32 states. It's probably deterministic already but manipulating 32-state automata is tedious and error-prone for us humans. – David Richerby Feb 4 '15 at 12:08
• @DavidRicherby Implement the algorithms from lecture then. That's a good exercise in any case. – Raphael Feb 4 '15 at 13:49

The idea of using remainders is perfect for the general problem of "Recognize base-$b$ strings representing a number divisible by $k$" for some general, fixed $b$ and $k$. However, it's not optimal for certain combinations of $b$ and $k$ where you can tell that the number is divisible by $k$ "just by looking at it." For example, if I asked you to recognize decimal numbers divisible by $100\,000$, you wouldn't be messing around with remainders: you'd use a nice textual property of decimal numbers divisible by powers of ten.
After building the automaton you can minimize it using standard constructions, to see if you cannot do with less states. Perhaps the same approach works for $2^n$, but then you not have a single "concrete" automaton. Alternatively you might use the theory of Myhill-Nerode equivalence classes of the language, to show the number of states is at least a certain number.
$L=\{ w \in \{0,1\}^* | w=xy$ and $x\in \{0,1\}^*$ and $(y=100000$ or $y=000000) \}$