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.
$\begingroup$
$\endgroup$
1
-
2$\begingroup$ They do generate the same strings. The real question is how to prove it. $\endgroup$– Dave ClarkeCommented Sep 27, 2012 at 14:20
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
6
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.
-
$\begingroup$ The string "1" is in the second language. Is it in the first? Maybe I'm misunderstanding the "+" notation. $\endgroup$– JoeCommented Sep 27, 2012 at 19:28
-
1
-
$\begingroup$ Thanks for the clarification, since "+" can also mean "1 or more" in many implementations of regular expressions. en.wikipedia.org/wiki/Regular_expression#Basic_concepts $\endgroup$– JoeCommented Sep 27, 2012 at 21:33
-
1$\begingroup$ @joe right, there is a kleene-plus, defined as $0^+ \equiv 00^*$. While the kleene-plus is a unary operator, the "or" sign is a binary operator. I agree this can be confusing. $\endgroup$– Ran G.Commented Sep 27, 2012 at 21:43
-
$\begingroup$ Wouldn't it be better to write it $(\{0\} \cup \{1\})^*$? $\endgroup$– phant0mCommented Sep 30, 2012 at 22:27
$\begingroup$
$\endgroup$
1
They are not the same. When we say $0+1$ it signifies a union operation, which is "either or". So either $0$ or $1$ can be present and the ${}^*$ indicates that it can be present any number of times.
On the other hand, $01$ is a concatenation of the symbols $0$ and $1$. So $(0^*1^*)$ means $0$ can occur any number of times followed by $1$ occurring any number of times and the outer asterisk denotes that such a sequence can occur in the string $n$ times.
-
1$\begingroup$ I'm not sure what your answer adds. It's already been established that the two regular expressions, while textually different, describe the same language (viz. $\{0,1\}^*$). Your answer doesn't even make clear that they do describe the same language: in fact, I can't even tell if you're trying to say, incorrectly, that the regular expressions match different languages. $X^*$ doesn't mean that a specific sequence matching $X$ "occurs in the string $n$ times": it means that the string can be broken into an arbitrary number of blocks, which may be different but each must match $X$. $\endgroup$ Commented Nov 5, 2014 at 12:28