equivalence

Question

2. Which of the following is true?
a) (01)*0 = 0(10)*
b) (0+1)*0(0+1)*1(0+1) = (0+1)*01(0+1)*
c) (0+1)*01(0+1)*+1*0* = (0+1)*
d) All of the mentioned

Answer 1

a)  is true as  we have regular expression identity : P(QP)*  =  (PQ)* P and here  P = 0 and Q = 1.

b)  will be true..I think there is misprint in the last of "  (0+1)*0(0+1)*1(0+1)  " there should be a '*" after last "(0+1)"..

c) is true as the complement of 1*0* is  (0+1)* 01 (0+1)*  as 1*0* means "any number of 1's followed by any number of 0's"..So in complementary language we should have at least one violation to this.Hence at least 1 "01" should be present in L'.

And we know  L union L'   =  Σ*  =  (0+1)*.  Hence c) is also true..

Hence D) should be correct answer..