Which one of the following regular expressions represents the set of all binary strings with an odd

Q: What is GATE-CS?

GATE-CS is a competitive examination conducted in India. This question is from the 2020 GATE-CS Theory of Computation paper.

Q: How can I prepare for GATE-CS Theory of Computation?

To prepare for GATE-CS Theory of Computation, practice previous year questions (PYQs), understand concepts thoroughly, and solve mock tests regularly. This 2020 question covers Regular Expressions topic.

Q: What is the difficulty level of this question?

This GATE-CS 2020 Theory of Computation question has a hard difficulty level and is marked as an important question.

Q: Where can I find more GATE-CS previous year questions?

You can find more GATE-CS previous year questions on AspirantMitraa. Browse by subject, topic, year, and difficulty level to practice effectively.

Question

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

Accepted Answer

Correct Answer: (B) (0*10*10*)*10*Concept -- Regular Expressions for Counting: A regular expression for binary strings with an odd number of 1s is required. Option B: (0*10*10*)*10* -- The part (0*10*10*)* generates zero or more groups each containing exactly two 1s (an even number of 1s). Then 10* adds exactly one more 1 (followed by zero or more 0s). Thus the total is an even number (possibly 0) plus 1, giving an odd number of 1s. This is the correct structure. Option A: ((0+1)*1(0+1)*1)*10* generates an even number of 1s from the starred part, then adds 1 more with 10*. However the (0+1)* parts inside can add more 1s, making the count unpredictable. Option C: 10*(0*10*10*)* starts with one 1 then adds pairs, but may miss strings starting with 0. Option D: (0*10*10*)*0*1 forces the string to end in 1, but strings with odd 1s need not end in 1 (e.g., '10' has one 1 but ends in 0). Option B correctly handles all cases.

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

Master GATE-CS with Our Test Series

More Questions from Regular Expressions

Frequently Asked Questions

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

Master GATE-CS with Our Test Series

More Questions from Regular Expressions

Frequently Asked Questions