The GATE Grind

GATE 2020 CS – Question 17

Theory of Computation · Regular Expressions and Finite Automata · 1 mark · Multiple choice

Which one of the following regular expressions represents the set of all binary strings with an odd number of 1's?

  1. $((0+1)^*1(0+1)^*1)^*10^*$
  2. $(0^*10^*10^*)^*0^*1$
  3. $10^*(0^*10^*10^*)^*$
  4. $(0^*10^*10^*)^*10^*$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) $10^*(0^*10^*10^*)^*$

Explanation

Options C and D both generate exactly the strings with an odd number of 1's (one 1 plus pairs of 1's). Option B cannot generate '10', and A generates only strings ending in 10*. The official key is MTA (marks to all).