GATE CS 2003 Q14 — Regular Expressions and Finite Automata

To find which regular expression is equivalent to $0^*(10^*)^*$, let us analyze the language generated by it.

Step 1: Analyze the given expression $0^*(10^*)^*$

Let the alphabet be $\Sigma = \{0, 1\}$.

• The term $0^*$ generates any number of $0$s (including the empty string $\epsilon$).
• The term $(10^*)^*$ generates any sequence of blocks, where each block starts with a $1$ followed by any number of $0$s.

Any string over $\{0, 1\}^*$ can be uniquely decomposed into an initial sequence of $0$s, followed by zero or more occurrences of a $1$ and its succeeding $0$s. For example, the string $00101100$ can be parsed as: $$\underbrace{00}_{0^*} \cdot \underbrace{10}_{10^*} \cdot \underbrace{1}_{10^*} \cdot \underbrace{100}_{10^*}$$ Thus, the regular expression $0^*(10^*)^*$ generates all possible strings over $\{0, 1\}$, which means: $$0^*(10^*)^* = (0+1)^*$$

Step 2: Analyze Option A: $(1^*0)^*1^*$

• The term $(1^*0)^*$ generates zero or more blocks, where each block consists of any number of $1$s followed by a single $0$.
• The term $1^*$ generates any trailing sequence of $1$s.

Any string over $\{0, 1\}^*$ can be decomposed into blocks of $1$s ending with a $0$, followed by any remaining $1$s at the end. For example, the string $00101100$ can be parsed as: $$\underbrace{0}_{1^*0} \cdot \underbrace{0}_{1^*0} \cdot \underbrace{10}_{1^*0} \cdot \underbrace{110}_{1^*0} \cdot \underbrace{0}_{1^*0} \cdot \underbrace{\epsilon}_{1^*}$$ Thus, this expression also generates all possible strings over $\{0, 1\}$: $$(1^*0)^*1^* = (0+1)^*$$ Since both expressions represent $(0+1)^*$, they denote the same set.

Step 3: Eliminate other options

• Option B: $0+(0+10)^*$
  This expression cannot generate any string containing consecutive $1$s (such as "11"), because every $1$ must be immediately followed by a $0$. Thus, it is not equal to $(0+1)^*$.
• Option C: $(0+1)^*10(0+1)^*$
  This expression only generates strings that contain the substring "10". It cannot generate strings like "0", "1", or "111". Thus, it is not equal to $(0+1)^*$.

Therefore, Option A is the correct choice.