Which one of the following regular expressions represents the set of all…
2020
Which one of the following regular expressions represents the set of all binary strings with an odd number of 1′s ?
- A.
\(((0+1)^*1(0+1)^*1)^*10^*\) - B.
\((0^*10^*10^*)^*0^*1\) - C.
\(10^*(0^*10^*10^*)^*\) - D.
None
Attempted by 134 students.
Show answer & explanation
Correct answer: D
A regular expression for all binary strings with an odd number of 1s must allow any number of 0s before, between, and after the 1s, and it must ensure that the count of 1s is odd.
One correct form is:
(0*10*10*)*0*10*
Here, each (0*10*10*) block contributes exactly two 1s, so its repetition contributes an even number of 1s. The final 0*10* contributes one additional 1, making the total count odd.
Now check the options:
A is not correct because (0+1)* inside the paired part can include extra 1s, so it can generate strings with an even number of 1s, for example 1111. It also misses valid strings such as 01.
B is not correct because it forces the string to end with 1. It rejects valid strings such as 10 and 1110, which have an odd number of 1s.
C is not correct because it forces the string to start with 1. It rejects valid strings such as 01.
Therefore, none of the given regular expressions is correct, so option D is the answer.