Question 57

The DFA recognizing binary strings divisible by 3 has states $q_0$ (remainder 0, start and accept state), $q_1$ (remainder 1), and $q_2$ (remainder 2):

• From $q_0$: on 0 goes to $q_0$; on 1 goes to $q_1$
• From $q_1$: on 0 goes to $q_2$; on 1 goes to $q_0$
• From $q_2$: on 0 goes to $q_1$; on 1 goes to $q_2$

Deriving expression via state elimination:

1. Eliminate state $q_2$:
   State $q_2$ has a self-loop on 1 ($1^*$).
   The path from $q_1$ through $q_2$ and back to $q_1$ is $0 1^* 0$.
   Thus, at $q_1$, the self-loop is $(0 1^* 0)^*$.
   From $q_1$, transitioning to $q_0$ on 1 gives the path expression $1 (0 1^* 0)^* 1$ from $q_0$ through $q_1$ back to $q_0$.
   Combining with the self-loop on 0 at $q_0$, the overall regular expression is:
   $$(0 + 1 (0 1^* 0)^* 1)^*$$
   This matches option A.

2. Equivalence of Option C:
   Using the regular identity $(R^* S^*)^* = (R + S)^*$, setting $R = 0$ and $S = 1(01^*0)^*1$ gives $(0^*(1(01^*0)^*1)^*)^* = (0 + 1(01^*0)^*1)^*$. Thus, option C represents the exact same language and is correct.

3. Eliminate state $q_1$ first:
   • From $q_0$, paths to $q_0$ directly: 0 and $11$.
   • Paths between $q_0$ and $q_2$: $q_0 \to q_1 \to q_2$ gives $10$, and $q_2 \to q_1 \to q_0$ gives $01$.
   • Self loop at $q_2$: 1 (direct) or $00$ (via $q_1$), giving $(1 + 00)$.
   • Connecting from $q_0$ through $q_2$ back to $q_0$ gives $10 (1 + 00)^* 01$.
   • Combined with direct loops at $q_0$, the expression is:
   $$(0 + 11 + 10(1 + 00)^* 01)^*$$
   This precisely matches option B.

Option D has the term $11(1+00)^*00$ instead of $10(1+00)^*01$, which produces invalid strings that are not multiples of 3 (for instance, $11100 = 28$, which is not divisible by 3). Therefore, option D is incorrect.