3
$\begingroup$

I was aware of the fact that, if DFA needs to accept binary string with its decimal equivalent divisible by $n$, then it can have minimum $n$ states.

However recently came across following text:

  • If $n$ is power of $2$
    Let $n=2^m$, so number of minimum states $=m+1$. For $n=8=2^3$, we need $3+1=4$ states.
  • Else If $n$ is odd
    Number of states $=n$. For $n=5$, we need $5$ states.
  • Else if $n$ is even
    Keep dividing it with $2$ until you get odd quotient. The result is final odd quotient plus number of divisions done. For $n=20,20/2=10,10/2=5→5+2=7$ states

I was guessing:
Q1. From where all these facts came. (I know this must have come from general pattern that such DFAs follow, but then I have below doubts)
Q2. Are these points indeed correct?
Q3. If yes (for Q2), then what can be the reason for each point?
Q4. Do these three bullet points cover all cases? (I guess yes, since there is even and odd, but I am new to this, and I was guessing if any such more point is left unmentioned in my textbook, especially since I did not find any reference book (by Peter Linz and Hopcroft-Ullman) talking about this topic)

$\endgroup$
  • $\begingroup$ There are a few things missing here. First, is the number input LSB to MSB or MSB to LSB? (Looks like LSB to MSB.) Second, are you allowing the empty string to represent zero? $\endgroup$ – Yuval Filmus Dec 23 '17 at 22:41
  • $\begingroup$ The way to prove such results is to twofold: first you prove an upper bound by constructing a DFA accepting the given language, then you prove a lower bound using Myhill–Nerode theory. $\endgroup$ – Yuval Filmus Dec 23 '17 at 22:42
  • $\begingroup$ For an example, see this: cs.stackexchange.com/questions/85785/…. $\endgroup$ – Yuval Filmus Dec 23 '17 at 22:53
  • $\begingroup$ Regarding Q4, yes, they cover all cases. I'm certain you can prove this in your own, even if you're new to "this" – this has nothing to do with automata theory. $\endgroup$ – Yuval Filmus Dec 23 '17 at 22:55
  • $\begingroup$ Can you provide any link discussing these two points: (1) LSB to MSB and MSB to LSB number input (2) Representing zero by empty string and possibly these two points in the context of "divisible by $n$ DFA" . Also I guess first point wont make number of states in min DFA to change. Second point might change it. $\endgroup$ – anir Dec 24 '17 at 7:02
2
$\begingroup$

Case 1: $n$ is a power of 2

If you wanted to check whether a decimal number is divisible by some power of 10, you can just look at the number of trailing zeros. For example, all numbers that are divisible by $100 = 10^2$ end with 2 zeros (this is of course including numbers ending with more than 2 zeros). The same idea can be applied here for binary numbers and powers of 2. Specifically to check for multiples of $n = 2^m$, you can simply check if the string ends in $m$ zeros. For example, if $n = 16 = 2^4$, all multiples of $n$ will end in 0000 (4 zeros). Thus we can create the following DFA for $n = 16$:

enter image description here

This construction can be extended to all multiples of 2, where you have $m+1$ states to ensure that your input ends in at least $m$ zeros (reading a 0 takes you one state forward, reading a 1 takes you back to the start). As suggested in the comments on your question, you can show that you can't do any better than this using a Myhill–Nerode argument.

Case 2: $n$ is odd

The general idea here is that when a number is divided by $n$, the possible remainders are $0, 1, \ldots, n-2$ or $n-1$. We can give our DFA one state for each of these possible remainders so as we process a string, we're keeping track of the remainder of what we've read so far and transitioning to the appropriate remainder based on what character we read. Then, we accept if we finish in the remainder 0 state.

Design DFA accepting binary strings divisible by a number 'n' walks through a detailed method for constructing such a DFA, and you can find out more about this by searching for "DFA based division". This gives a total of $n$ states, which is optimal by Myhill-Nerode because these remainders are exactly the equivalence classes given by the relation $\equiv_L$ for the language $L = \{\text{binary strings divisible by }n\}$.

Case 3: $n$ is even (and not a power of 2)

The technique in case 2 also works here but it isn't optimal. Every $n$ in this case can be expressed as $2^km$ where $m$ is odd (this is the division procedure described in your question). Thus, to check whether a binary string is divisible by $n$, we check whether it is divisible by both $2^k$ and $m$.

We know that it takes $k$ states to check divisibility by $2^k$ (case 1) and $m+1$ states to check divisibility by $m$ (case 2). We can take a DFA for divisibility by $m$, unmark the accepting state and make it the start state for a DFA for divisibility by $2^k$, giving our final DFA $k+m$ states.

As an example, here's the DFA for $n = 6$:

enter image description here

The top three states ensure that the number is a multiple of 3, and the final accept state ensures that it is a multiple of 2.

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