2
$\begingroup$

I came across this weird expression while learning about regular expressions.

$R^+ \cup \varepsilon = R^*$

why does doing union with an empty string makes this regex go from 1 or more to 0 or more?

$\endgroup$
4
  • 6
    $\begingroup$ There is a bit of an abuse of notations between the empty string, the regular expression that matches just the empty string, and the singleton set that contains only the empty string. $\endgroup$
    – Stef
    Feb 9 at 21:01
  • 3
    $\begingroup$ It looks like you've gotten help that worked for you, which is great. But in the future, you may get better answers if you explain a bit more about what's going on in your head. Answering a question of the form "Why does X happen?" requires much more guesswork about what's gone wrong with your reasoning than "Why does X happen? I expected Y to happen instead." does. $\endgroup$ Feb 10 at 2:04
  • $\begingroup$ sure @DanielWagner I'll keep that in mind. $\endgroup$
    – hxdshell
    Feb 10 at 2:23
  • $\begingroup$ Compare the equivalent POSIX notation: (.+)|() = .* $\endgroup$
    – OrangeDog
    Feb 10 at 13:49

1 Answer 1

6
$\begingroup$

Regular expressions represent sets of strings, so $\varepsilon$ in that expression represents the set that contain only the 0 length string, $\{\varepsilon\} $. This of course is not the same as the empty set $\emptyset$, so the union will add the empty string to the set that does not contain an empty string ($R^+$) , hence the regular expression $R^*$ is the set of strings that contains 0 length (empty) string and non-zero length string.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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