Question 17

Examine the component parts of the expressions:

• In option D, $(0^* 1 0^* 1 0^*)^* 1 0^*$:
  • The sub-expression inside the Kleene star, $(0^* 1 0^* 1 0^*)$, contains exactly two 1's surrounded by arbitrary runs of 0's. Any repetition of this block generates an even count of 1's ($0, 2, 4, 6, \dots$).
  • Following the star, the term $1 0^*$ contributes exactly one additional 1, bringing the grand total of 1's to an odd number ($1, 3, 5, 7, \dots$).

Why other options fail:

• Option A: $((0 + 1)^* 1 (0 + 1)^* 1)^* 1 0^*$ contains $(0+1)^*$ which can itself generate arbitrary numbers of 1's, so the count is not guaranteed to be odd.
• Option B: $(0^* 1 0^* 1 0^*)^* 0^* 1$ requires the string to end with a 1, failing to match strings with an odd count of 1's that end in 0 (e.g., '10').
• Option C: $1 0^* (0^* 1 0^* 1 0^*)^*$ requires the string to begin with a 1, failing to match strings that begin with 0 (e.g., '01').

Note on official key: While option D omits strings with leading 0's before the first 1 (such as '01'), IIT Delhi retained option D as the official answer.