Question

Which of the following regular expressions represent(s) the set of all binary numbers that are divisible by three? Assume that the string $\epsilon$ is divisible by three.

• A. $(0 + 1(01^*0)^*1)^*$
• B. $(0 + 11 + 10(1 + 00)^*01)^*$
• C. $(0^*(1(01^*0)^*1)^*)^*$
• D. $(0 + 11 + 11(1 + 00)^*00)^*$

Hint:

Regular expressions for divisibility properties are best verified by mapping them to cycles of the corresponding modulo DFA.

Answer 1

The Correct Option is A, B, C

Step 1: Recall the automaton for binary numbers divisible by 3.
Binary numbers divisible by $3$ are recognized by a DFA with three states corresponding to remainders $0$, $1$, and $2$ modulo $3$. The start and accepting state corresponds to remainder $0$. Any correct regular expression must generate exactly the strings accepted by this DFA, including the empty string $\epsilon$.

Step 2: Analyse option (A).
The expression $(0 + 1(01^*0)^*1)^*$ correctly captures cycles that return the automaton to the remainder-$0$ state. The outer Kleene star allows repetition of such cycles, including $\epsilon$. Hence, it generates exactly all binary strings divisible by $3$.

Step 3: Analyse option (B).
The expression $(0 + 11 + 10(1 + 00)^*01)^*$ also corresponds to concatenations of substrings that map the DFA from remainder $0$ back to remainder $0$. This structure correctly represents all valid transitions of the modulo-$3$ automaton. Thus, option (B) is correct.

Step 4: Analyse option (C).
The expression $(0^*(1(01^*0)^*1)^*)^*$ allows any number of leading zeros and valid remainder-$0$ cycles. Since leading zeros do not change divisibility by $3$, and the inner structure ensures modulo-$3$ correctness, this expression also represents the desired language. Hence, option (C) is correct.

Step 5: Analyse option (D).
The expression $(0 + 11 + 11(1 + 00)^*00)^*$ does not correctly correspond to all remainder-$0$ transitions in the modulo-$3$ DFA and fails to generate some valid binary multiples of $3$. Therefore, it is incorrect.

Step 6: Conclusion.
The regular expressions that correctly represent the set of all binary numbers divisible by $3$ are given in options (A), (B), and (C).