Let N be any positive integer, then is following language regular for every $N$?

$L$ = { $B_n : B_n(modN) == 0$ } where $B_n$ is binary representation of a number.

E.g, $L=\lbrace B_n : B_nmod31 == 0,B_n \ is \ a \ binary \ number \rbrace$ is regular? Will the language be regular for any positive number in place of $31$.


You can produce a finite automaton to recognize binary strings divisible by $N$ for any $N>0$. Use $N+1$ states, $s$ (the start state) and $q_i$, where being in state $q_i$ corresponds to having seen input $B$ which is congruent to $i\bmod N$.

The transitions are then easy enough: in state $q_i$ and seeing a $0$ input the machine would pass to state $q_k$, where $k\equiv 2i\bmod N$, since appending a zero to a binary string doubles the number represented. Similarly $\delta(q_i, 1)=q_k$, where $k\equiv 2i+1\bmod N$.

The start state is there solely to avoid the question of what number the empty string represents, and obviously $q_0$ is the final state.

  • $\begingroup$ How can we ensure the edges is transition graph made according to you won't result in accepting other languages? $\endgroup$ – Mr. Sigma. Dec 13 '17 at 3:30
  • $\begingroup$ @Tamas. Try it for $N=3$ to see what's going on. The only strings in the language are precisely those representing numbers divisible by 3, in this case $\endgroup$ – Rick Decker Dec 13 '17 at 13:46
  • $\begingroup$ I have made for 3 or 4. Not sure it will work correctly for all or not. $\endgroup$ – Mr. Sigma. Dec 13 '17 at 14:06
  • $\begingroup$ @Tamas. Instead, it might help to ask "How could this not work?" $\endgroup$ – Rick Decker Dec 13 '17 at 17:20

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.