GATE CS 2010 Q39 — Regular Expressions and Finite Automata

The language $L$ contains all binary strings with an even number of $1$s (including zero $1$s, i.e., $0, 00, 000, \dots$).

• Option A: $(0^*10^*1)^*$ cannot generate the string $0$, which belongs to $L$ because it has zero $1$s (an even number).
• Option C: $0^*(10^*1)^*0^*$ cannot generate the string $1010101$ (which has four $1$s). In $(10^*1)^*$, any two consecutive iterations result in $10^a110^b1$, meaning the second and third $1$s must be adjacent with no $0$ between them.
• Option D: $0^*1(10^*1)^*10^*$ requires at least two $1$s, so it cannot generate $0$.
• Option B: $0^*(10^*10^*)^*$ correctly generates all strings with an even number of $1$s. Any string with $2k$ ones can be partitioned as $0^{n_0} (1 0^{n_1} 1 0^{n_2}) (1 0^{n_3} 1 0^{n_4}) \dots (1 0^{n_{2k-1}} 1 0^{n_{2k}})$, which perfectly matches this regular expression.