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