2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I've a feeling that this question is a duplicate but I couldn't find the dupe. $\endgroup$ – David Richerby Dec 15 '14 at 10:29
  • $\begingroup$ @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. $\endgroup$ – Hendrik Jan Dec 15 '14 at 15:29
  • $\begingroup$ @HendrikJan That was probably what I was thinking of! $\endgroup$ – David Richerby Dec 15 '14 at 15:43
  • $\begingroup$ @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). $\endgroup$ – Gilles Jan 17 '15 at 13:43
8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Abhishek Dec 15 '14 at 11:53
  • $\begingroup$ 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. $\endgroup$ – David Richerby Dec 15 '14 at 12:33
  • $\begingroup$ That's a good suggestion, David. I'll incorporate that line of thought. $\endgroup$ – Abhishek Dec 16 '14 at 5:13

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.