GATE CS 1998 Q1.12 — Regular Expressions and Finite Automata

To find which regular expressions do not represent the string $1101$, we test the string against each option:

1. $110^*(0 + 1)$

   We can match $1101$ by choosing:

   • $11$ from the prefix
   • $0^1 = 0$ from $0^*$
   • $1$ from $(0 + 1)$

   This yields $11 \cdot 0 \cdot 1 = 1101$. Thus, $1101$ belongs to this set.

2. $1(0 + 1)^*101$

   We can match $1101$ by choosing:

   • $1$ from the prefix
   • $\epsilon$ (empty string) from $(0 + 1)^*$
   • $101$ from the suffix

   This yields $1 \cdot \epsilon \cdot 101 = 1101$. Thus, $1101$ belongs to this set.

3. $(10)^*(01)^*(00 + 11)^*$

   Let's attempt to match $1101$:

   • Since $1101$ starts with $11$, and $(10)^*$ can only generate strings starting with $10$ (or $\epsilon$), we must choose $\epsilon$ from $(10)^*$.
   • Now we must match $1101$ with $(01)^*(00 + 11)^*$. Since $(01)^*$ can only generate strings starting with $0$ (or $\epsilon$), we must choose $\epsilon$ from $(01)^*$.
   • This leaves $(00 + 11)^*$ to match $1101$. We can match the first two characters $11$ using the $11$ block, leaving $01$. However, $(00 + 11)^*$ cannot generate $01$.

   Thus, $1101$ does not belong to this set.

4. $(00 + (11)^*0)^*$

   Observe the terms inside the outer Kleene star:

   • $00$ ends with $0$.
   • $(11)^*0$ ends with $0$.

   Since both constituent blocks end with $0$, any non-empty string generated by this regular expression must end with $0$. Since $1101$ ends with $1$, it cannot be generated.

   Thus, $1101$ does not belong to this set.

Therefore, the string $1101$ does not belong to the sets represented by C and D.