[Solved]: Difference between regular expressions: $(0^*1^*)^*$ and $(0+1)^*$

Problem Detail: 

Can anyone tell me what is the difference between the following regular expressions: $(0^*1^*)^*$ and $(0+1)^*$ ? To me they look like generating the same string.

Asked By : Abhishek Anand

Answered By : Ran G.

The language of both regular expressions is the same, $L((0+1)^*)=L((0^*1^*)^*)$. This follows from the following three claims:

Claim 1:

if $L_1 \subseteq L_2$, then $L_1^* \subseteq L_2^*$.

Claim 2:

$L(0+1) \subseteq L(0^*1^*)$

Claim 3:

$ (0^*1^*)^* \subseteq (0+1)^* \equiv \Sigma^*$

The 2nd and 3rd claims are trivial. Prove the first claim and you're done.

Note however, that the two regular expressions are not the same (ie., they are different!). They are equivalent in the sense of the language they generate. They are different in the way they generate it.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/4761