0

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.

Andrés E. Caicedo
  • 79,201
confused_student
  • 11
  • For each integer $n,$ you need to come up with a corresponding finite automaton or regular expression that's designed specifically to identify multiples of $n.$ I would go with a DFA. – Mitchell Spector Sep 20 '16 at 01:04

1 Answers1

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.

Brian M. Scott
  • 616,228
  • Yes, that's the DFA I had in mind when I posted a tip earlier. There's one slight trick though: you should have separate initial and final states so that you don't accept the empty string. Those two states would have exactly the same transitions out of them (based on $k$ being $0$ mod $n).$ All transitions from another state to $0$ should go to the one marked as a final state. – Mitchell Spector Sep 23 '16 at 18:59
  • @Mitchell: I was deliberately accepting the empty string, but you’re probably right in thinking that it isn’t wanted here. – Brian M. Scott Sep 23 '16 at 19:00
  • Yes, the empty string logically should be a binary number representing $0,$ but it's not :) . – Mitchell Spector Sep 23 '16 at 19:02
  • @Mitchell: I actually have encountered contexts in which it was to be so treated, though they’re certainly less common. – Brian M. Scott Sep 23 '16 at 19:04
  • In fact, arguably the binary representation of 0 should be the empty string, rather than the string "0", on the principle that a binary number shouldn't start with a '0' character. – Mitchell Spector Sep 23 '16 at 19:06