GATE CS 2009 Q15 — Regular Expressions and Finite Automata

To determine the language described by the regular expression $R = (0+1)^*0(0+1)^*0(0+1)^*$, let us analyze its structure:

• The term $(0+1)^*$ represents any arbitrary string (including the empty string $\epsilon$) over the alphabet $\{0, 1\}$.
• The expression contains two explicit $0$'s separated and surrounded by $(0+1)^*$.

This structure guarantees that any string matching this regular expression must contain at least two $0$'s. There are no restrictions on the characters appearing before the first $0$, between the two $0$'s, or after the second $0$.

Thus, the language represents the set of all strings containing at least two $0$'s.

Elimination of Other Options:

• Option A: The string $010$ is generated by the regular expression, but it does not contain the substring $00$. Thus, Option A is incorrect.
• Option B: The string $000$ contains three $0$'s and is generated by the regular expression. This contradicts "at most two $0$'s". Thus, Option B is incorrect.
• Option D: The string $0$ begins and ends with $0$, but it cannot be generated by the regular expression (as it has only one $0$). Thus, Option D is incorrect.