Question

Let L = $\left\{\omega ϵ\right(0+1{)}^{\ast }\mid \omega hasevennumberof1s\}$

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^{\ast }1({10}^{\ast }1{)}^{\ast }{10}^{\ast }$
• B. $0^{\ast }({10}^{\ast }{10}^{\ast }{)}^{\ast }$
• C. $(0^{\ast }{10}^{\ast }1{)}^{\ast }$
• D. $0^{\ast }({10}^{\ast }1{)}^{\ast }{0}^{\ast }$

Answer 1

The correct option is B $0^{\ast }({10}^{\ast }{10}^{\ast }{)}^{\ast }$

Choice (a) $(0^{\ast }{10}^{\ast }1{)}^{\ast }$

will always generate strings ending with 1. But we want an expression for bit strings with even no of 1's, which includes strings like "110" which ends with 0.

So, choice(a) is not correct.

Choice (c) $0^{\ast }({10}^{\ast }1{)}^{\ast }{0}^{\ast }$

"1010101" $\notin$ $0^{\ast }({10}^{\ast }1{)}^{\ast }{0}^{\ast }$

but "1010101" has even number of 1's. So choice (c) is incorrect.

Choice (d) $\lambda$ $\notin$$0^{\ast }1({10}^{\ast }1{)}^{\ast }{10}^{\ast }$

but "$\lambda$" is a bit string with even no of 1's (zero 1's). So choice (d) is incorrect.

Choice (b) can generate all bit strings with even no of 1's. So choice (b) is correct.