2
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ They do generate the same strings. The real question is how to prove it. $\endgroup$ Sep 27 '12 at 14:20
9
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ The string "1" is in the second language. Is it in the first? Maybe I'm misunderstanding the "+" notation. $\endgroup$
    – Joe
    Sep 27 '12 at 19:28
  • 1
    $\begingroup$ @Joe the + sign is OR, sometimes it is written as | (like in: wikipedia). So $0+1$ means $0$ or $1$, and the string 1 is in the language. $\endgroup$
    – Ran G.
    Sep 27 '12 at 19:47
  • $\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$
    – Joe
    Sep 27 '12 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.
    Sep 27 '12 at 21:43
  • $\begingroup$ Wouldn't it be better to write it $(\{0\} \cup \{1\})^*$? $\endgroup$
    – phant0m
    Sep 30 '12 at 22:27
-3
$\begingroup$

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.

$\endgroup$
1
  • 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$ Nov 5 '14 at 12:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.