For $n\ge 1$ let $A_n =\{w\in\{0,1\}^∗\mid w$ is a binary number that is a multiple of $n\}$, and prove that $A_n$ is regular.

Question

For $n\ge 1$ let

$$A_n =\{w\in\{0,1\}^*\mid w\text{ is a binary number that is a multiple of }n\}\;.$$

Prove that $A_n$ is regular.

Hi. This is a problem for my finite automata class, so I don't expect an outright answer (though I wouldn't mind because it would still teach me how to do these problems in the future). However, I do hope for a push in the right direction. I wouldn't be here if I weren't at an absolute loss on how to proceed though. If there are any sample problems that would be great too! If I figure it out I will post the solution. A big confusion for me is how does $n$ matter? It seems important to finding the answer.

Answer 1

HINT: You can do it by constructing a DFA that recognizes $A_n$. Such a DFA can be constructed with $n$ states, $q_0,q_1,\ldots,q_{n-1}$; $q_0$ will be both the initial state and the only acceptor (final) state. The transition function should be designed so that after reading an input that is the binary representation of some integer $k$, the DFA is in state $q_{k\bmod n}$. For instance, if $n=5$ and the input is $1101$, the binary representation of $13$, $13\bmod 5=3$, and the DFA should be in state $q_3$.

Suppose that the input string is $b_1\ldots b_m$. If you read this string one bit at a time from left to right, you could calculate the number that it represents in the following way. Let $k_1=b_1$. If we’ve calculated $k_i$ for some $i<m$, let $k_{i+1}=2k_i+b_{i+1}$. Then $k_m$ is the value of the binary string.

Example: If the input is $\color{crimson}1\color{blue}1\color{green}01$, we have $k_1=\color{red}1$, $k_2=2\cdot1+\color{blue}1=3$, $k_3=2\cdot3+\color{green}0=6$, and $k_4=2\cdot6+1=13$.

Doubling a number doubles its remainder on division by $n$, so if $n=5$, and the DFA is in state $q_1$, it should go to $q_{2\cdot1}=q_2$ on reading a $0$ and to $q_{2\cdot1+1}=q_3$ on reading a $1$. If it’s in state $q_3$, it should go to $q_1$ on reading a $0$ and to $q_2$ on reading a $1$, since $(2\cdot3)\bmod 5=1$.

Added: Note that this DFA accepts the empty string as a representation of $0$. If this is not wanted, you’ll need another state, $q_n$, to be the acceptor state, leaving $q_0$ as the initial state. The minor modification is very straightforward.