The GATE Grind

GATE 2020 CS – Question 17

Theory of Computation · Regular Expressions and Finite Automata · 1 mark · MTA

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: MTA

Explanation

The official GATE 2020 key awards marks to all for technical Q7, stored here as Q17 after the ten General Aptitude questions. No particular option is required for scoring. The previous explanation should not claim that C is uniquely correct or that its leading-1 expression generates strings with arbitrary leading zeros.

Official paper and key: https://gate2026.iitg.ac.in/doc/download/2020/cs_2020.pdf

More Regular Expressions and Finite Automata questions

All Regular Expressions and Finite Automata questions →