GATE CS 2021 Set 2 Q47 — Regular Expressions and Finite Automata

To find the regular expressions representing binary numbers divisible by $3$, we construct the state transition diagram (DFA) where the states represent the remainder modulo $3$:

• $q_0$ (remainder $0$): Start and accepting state.
• $q_1$ (remainder $1$): Non-accepting state.
• $q_2$ (remainder $2$): Non-accepting state.

The transition rules for a binary input $x$ are $q_{new} = (2 imes q_{old} + x) \pmod 3$:

• From $q_0$: on $0 \to q_0$, on $1 \to q_1$
• From $q_1$: on $0 \to q_2$, on $1 \to q_0$
• From $q_2$: on $0 \to q_1$, on $1 \to q_2$

Option A & C:

Eliminating state $q_2$ first, the self-loop at $q_1$ via $q_2$ becomes $01^*0$. The path from $q_0$ to $q_1$ and back to $q_0$ becomes $1(01^*0)^*1$. Combining this with the self-loop $0$ at $q_0$, we get the regular expression:

This matches Option A. Since $(R^*S^*)^*$ is equivalent to $(R+S)^*$, we can rewrite this as $(0^*(1(01^*0)^*1)^*)^*$, which matches Option C.

Option B:

If we eliminate state $q_1$ first:

• The path $q_0 \to q_1 \to q_0$ gives a self-loop of $11$ on $q_0$.
• The path $q_2 \to q_1 \to q_2$ gives a self-loop of $00$ on $q_2$.
• The transition $q_0 \to q_1 \to q_2$ becomes $10$.
• The transition $q_2 \to q_1 \to q_0$ becomes $01$.

Now, the simplified system has states $q_0$ and $q_2$:

• Self-loops on $q_0$: $0 + 11$
• Self-loops on $q_2$: $1 + 00$
• Path from $q_0$ to $q_2$ and back: $10(1+00)^*01$

Eliminating $q_2$ yields the regular expression:

This matches Option B.

Option D:

The binary representation of $9$ is $1001_2$, which is divisible by $3$. However, Option D cannot generate $1001_2$ because any string starting with $1$ must begin with $11$ according to its terms, whereas $1001_2$ starts with $10$. Thus, Option D is incorrect.