Project ForgeLet L = {w ∈ (0+1)* | w has even number of 1s}, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expressions below represents L?
- A(0*10*1)*
- 0*(10*10*)*
- C0*(10*1)*0*
- D0*1(10*1)*10*
Explanation
Testing (A) on '1010' (two 1s, valid, but with a trailing 0): no valid split into '0*10*1' chunks exists (each chunk must END in '1', but the string ends in '0'), so (A) fails to generate this valid string. Testing (B) 0*(10*10*)* on '1010': one repetition '10*10*' matches '1'+'0'(as the middle 0*)+'1'+'0'(trailing 0*) — full match. (B) correctly generates all even-1s strings including trailing zeros, and correctly excludes odd-1s strings (a single '1' can't complete a full 'X0*Y0*' repetition needing two 1s).
Source: GATE CS 2010 (2010)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.