GATE CS 2020 Set 1 — Question 17

This question was awarded 'Marks to All' in GATE 2020 because none of the options are correct.Analysis of Options:

• Option (A): $((0+1)^*1(0+1)^*1)^*10^*$

The sub-expression $(0+1)^*$ generates any binary string, including those with 1s. Thus, the inner part $((0+1)^*1(0+1)^*1)$ does not guarantee an even number of 1s. Consequently, the entire expression does not strictly generate strings with an odd number of 1s.

• Option (B): $(0^*10^*10^*)^*0^*1$

This expression generates strings ending in 1. It cannot generate strings like "10", which has an odd number of 1s. Thus, it does not represent all such strings.

• Option (C): $10^*(0^*10^*10^*)^*$

This expression generates strings starting with 1. It cannot generate strings like "01", which has an odd number of 1s.

• Option (D): $(0^*10^*10^*)^*10^*$

This expression generates strings where the first part has an even number of 1s (or zero), followed by a 1, then 0s. It cannot generate "01" because the first part $(0^*10^*10^*)^*$ cannot generate a single "0" (it must generate pairs of 1s or empty string $\epsilon$). If the first part is $\epsilon$, the string must start with 1. Thus "01" is missing.Since no option covers all binary strings with an odd number of 1s, the question is incorrect.