# Language of binary strings divisible by 7

There was a question something like, "Consider the language of all integers converted to binary form. The language of all strings divisible by 7 is :

1) Recognizable by a finite-automaton.

2) Recognizable by a Non-deterministic finite-automaton.

3) Recognizable by a deterministic Pushdown Automaton.

4) Recognizable by a Non-deterministic Pushdown Automaton.

5) Not recognizable by any of the above.

I'm curious to know the answer and its reason.

• I've a feeling that this question is a duplicate but I couldn't find the dupe. – David Richerby Dec 15 '14 at 10:29
• @DavidRicherby In the past I had a picture for "divisible by 3", which is similar to what you describe in your answer below, but has no explanation at all. – Hendrik Jan Dec 15 '14 at 15:29
• @HendrikJan That was probably what I was thinking of! – David Richerby Dec 15 '14 at 15:43
• @DavidRicherby There's also Language of the values of an affine function which is more general (but not really a duplicate because the generality makes it harder to follow). – Gilles Jan 17 '15 at 13:43

The langauge is regular, so answers 1–4 are all correct.

The (deterministic) automaton has seven states, $0, \dots, 6$ corresponding to the remainder when the number is divided by 7. The initial state is $0$, which is also the only accepting state. We adopt the convention that the empty string represents zero (as does the string "$0$", obviously).

To describe the transition function, suppose you're reading in some binary string and the bits you've read so far correspond to the natural number $n$ and the state you're in is $r=n\%7$ (the remainder when $n$ is divided by $7$). Let the next bit be $b\in\{0,1\}$. When you read that, you'll have seen the number $2n+b$, so you need to move to state

$$r' = (2n+b)\%7 = (2r+b)\%7\,.$$

And, of course, there's nothing special about $7$.

• Thanks for taking the time to reply, David. Its indeed not immediately obvious how a binary number can be recognized by a finite automaton. Remainders didn't occur to me at all. I was thinking "too loftily" about divisibility rules of 7, multiple-stacks etc. – Abhishek Dec 15 '14 at 11:53
• Remainders occurred to me immediately but that's because one of the research projects I'm working on at the moment involves a lot of modular arithmetic. How would a "normal person" come to the same conclusion? One line of thought is that if it can be done with a DFA at all (which I agree isn't at all obvious; a priori, maybe you do need a stack or even more), you must be able to encode everything you need to know in a finite number of states and be able to manipulate those states easily. For divisibility, remainders do encode the essence of the problem and they can be manipulated simply. – David Richerby Dec 15 '14 at 12:33
• That's a good suggestion, David. I'll incorporate that line of thought. – Abhishek Dec 16 '14 at 5:13