Let L = { w in (0 + 1)* | w has an even number of 1s }. That is, L is the set…
2010
Let L = { w in (0 + 1)* | w has an even number of 1s }. That is, L is the set of all bit strings with an even number of 1s. Which one of the following regular expressions represents L?
- A.
(0*10*1)*
- B.
0*(10*10*)*
- C.
0*(10*1)*0
- D.
0*(10*1)*10*
Attempted by 142 students.
Show answer & explanation
Correct answer: B
Correct regular expression: 0*(10*10*)*
The initial 0* allows any number of leading zeros, including pure-zero strings and the empty string.
Each block 10*10* contains exactly two 1s. Repeating this block any number of times therefore always adds 1s in pairs. So every generated string has an even number of 1s.
Conversely, any binary string with an even number of 1s can be read as some leading zeros followed by pairs of 1s, with any number of zeros between and after the two 1s in each pair.
Therefore, 0*(10*10*)* represents exactly the language L.
A video solution is available for this question — log in and enroll to watch it.