0
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – babou Feb 4 '15 at 10:46
  • $\begingroup$ 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. $\endgroup$ – babou Feb 4 '15 at 10:55
  • $\begingroup$ Build any FA, determinise, minimise. What's the problem? $\endgroup$ – Raphael Feb 4 '15 at 12:04
  • $\begingroup$ @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. $\endgroup$ – David Richerby Feb 4 '15 at 12:08
  • $\begingroup$ @DavidRicherby Implement the algorithms from lecture then. That's a good exercise in any case. $\endgroup$ – Raphael Feb 4 '15 at 13:49
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

Binary numbers that are divisible by 32 are ending in zero's. You can just keep track of how many consecutive zero's we have seen. If you want to answer the same question for the decimal alphabet, yes, then you need to worry about remainders modulo 32. The phrase "decimal equivalent" is a bit confusing here: divisibility of a number does not change when choosing another representation.

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.

$\endgroup$
0
$\begingroup$

Binary string whose decimal equivalent is divisible by 32 is the following language

$L=\{ w \in \{0,1\}^* | w=xy$ and $ x\in \{0,1\}^*$ and $(y=100000$ or $y=000000) \}$

If you try to construct the minimal DFA for it you'll find that after the initial state we have new state only when read another 0 and by reading 5 zeros we won't get new states.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.