GATE CS 1996 Q1.8 — Regular Expressions and Finite Automata

Let us analyze the language generated by each regular expression over the alphabet $\{0\}$:

1. $(00)^*(\varepsilon + 0)$: The term $(00)^*$ generates all even-length strings of $0$s: $\{\varepsilon, 00, 0000, \dots\}$. Concatenating this with $(\varepsilon + 0)$ gives: $$(00)^*(\varepsilon + 0) = (00)^*\varepsilon + (00)^*0 = (00)^* + (00)^*0$$ Since $(00)^*$ generates all even-length strings and $(00)^*0$ generates all odd-length strings, their union generates all possible strings of $0$s: $\{\varepsilon, 0, 00, 000, \dots\} = 0^*$.
2. $(00)^*$: Generates only even-length strings of $0$s: $\{\varepsilon, 00, 0000, \dots\}$.
3. $0^*$: Generates all strings of $0$s of any length: $\{\varepsilon, 0, 00, 000, \dots\}$.
4. $0(00)^*$: Generates only odd-length strings of $0$s: $\{0, 000, 00000, \dots\}$.

Thus, expressions (i) and (iii) both represent the language $0^*$ and are equivalent.