GATE CSE 2020 Q17: Regular expression for binary strings with an odd number of 1s
- Theory of Computation
- 1 mark
- MCQ
- −1/3 if wrong
Question
Which one of the following regular expressions represents the set of all binary strings with an odd number of 1's?
The official answer key gives marks to all for this question, so there is no answer to check. It is shown for practice and discussion.
Show answer and explanation
Answer: Marks to all (official GATE 2020 final answer key)
Concept used: Pair up 1s with and add one extra 1; check that every string with an odd count, including those starting with 0, is generated.
First step: Test short strings such as 01, 010 and 1 against each expression. The official key gives marks to all.
Full step-by-step solution
Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.
Share this question
Source: official GATE 2020 CS question paper and final answer key, organised by IIT Delhi. Question paper · Answer key
More Theory of Computation PYQs
- 2026 Session 1 · Q25Ambiguity of S → aSbS | bS | ε
- 2026 Session 1 · Q26Impossible minimal DFA sizes for a 6-state NFA
- 2026 Session 1 · Q51What follows from L1 ∩ L2 and L2 being regular
- 2026 Session 1 · Q52Counts of a's and b's in strings of a given CFG
- 2026 Session 2 · Q13Meaning of a Turing machine deciding a language
- 2026 Session 2 · Q29Which of four grammars are ambiguous