Let L = {w = (0+1)* | w has even number of 1's}, i.e. L is the set of all bit…
2016
Let L = {w = (0+1)* | w has even number of 1's}, i.e. L is the set of all bit strings with even number of 1's. Which one of the regular expression below represents L ?
- A.
(0*10*1)*
- B.
0*(10*10*)*
- C.
0*(10*1*)*0*
- D.
0*1(10*1)10*
Attempted by 72 students.
Show answer & explanation
Correct answer: B
The language L contains all bit strings with an even number of 1s, including zero 1s. The correct regular expression must allow any number of 0s while ensuring 1s occur in pairs. Option B, 0*(10*10*)*, begins with any number of leading zeros. The group (10*10*) captures a pair of 1s with optional zeros in between and after. The outer star repeats this group, guaranteeing an even total count of 1s. This covers the empty string and strings like 0, 11, and 101.