I'm not exactly sure what this question is asking me to do:

Show that the set of binary integers (given as strings over $\{0, 1\}$) that are divisible by $3$ is regular, by giving a DFA that recognizes it. Leading 0s are allowed. The empty string should be accepted. Briefly explain your answer.

Is this asking me to construct a DFA where the set of binary integers add up to be divisible or the number of elements is divisible?

I understand that by constructing the DFA I prove that it is regular.

  • 2
    $\begingroup$ The question asks you to construct a DFA that accepts a binary string iff this string represents a binary number that is divisible by 3. For example, 0100 should not be accepted, as it represents the number 4, which is not divisible by 3. The string 1001 should be accepted, as it represents 9. $\endgroup$ – Shaull Sep 29 '14 at 15:21

The question asks you to construct a DFA for the language

$$L = \{x \in \{0,1\}^* : x \text{ is the binary representation of an integer that is divisible by three}\}.$$

In other words, the DFA should accept a string if and only if this string is the binary representation of a number that is divisible by three.

  • $\begingroup$ Writing "$x$ is divisible by 3" is unclear when $x$ is a string. It would be more accurate to define $val(x)=\sum_{i=1}^n 2^{n-i}x_i$ where $x_i$ is the i-th bit of $x$. $\endgroup$ – Shaull Sep 29 '14 at 16:33

Hint: Make three states, $q_0, q_1, q_2$, representing the fact that in state $q_i$ you have seen a string of 0s and 1s that, when interpreted as a binary number, represents a number with remainder of $k$ when divided by 3. For example, having read $\mathtt{00101}$, the FA would be in state $q_2$, since the binary string $\mathtt{00101}$ corresponds to the decimal value 5, which has a remainder of 2 when divided by 3.

Now fill in the transitions: If, say we're in state $q_2$ having read a string that corresponds to a number $n$, what state would the FA be on reading a $\mathtt{0}$? What happens when you add a zero to the right of the representation of $n$, going, say from $\mathtt{00101}$ to $\mathtt{001010}$? Use this idea to fill in all the transitions and then decide what the final state(s) should be.

  • $\begingroup$ Ah! My personal favourite automaton. $\endgroup$ – Hendrik Jan Sep 29 '14 at 20:57
  • $\begingroup$ @HendrikJan. Oops. I didn't think of looking for an old answer first. Sorry for stepping on your toes $\endgroup$ – Rick Decker Sep 29 '14 at 21:04
  • $\begingroup$ No, my toes were certainly not hurt. Sorry if I made that impression. I hesitated to give the link, as you are kindly guiding towards a solution, where I blurt it out. Couldn't resist though. $\endgroup$ – Hendrik Jan Sep 29 '14 at 21:30

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.