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.
Difference between regular expressions: $(0^*1^*)^*$ and $(0+1)^*$
formal languages;regular languages;regular expressions
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.