0
$\begingroup$

On https://regexr.com/, using the default JavaScript (Browser) engine, the languages $L(a^*|b^*)$ and $L(b^*|a^*)$ are not the same. The first one matches only $a$'s and the second one $b$'s.

Is this a bug? Or does the site something different than evaluating regular expressions, as I learned them in class?

$\endgroup$
5
  • $\begingroup$ If you try the regexp (cre|rea), you'll find that the tool only reports one match (cre) within create: its does not handle overlaps. It has a bias on the left when detecting all the matches. Finding matches in a text, however, is not the same thing as considering the language of the regexp. $\endgroup$
    – chi
    Commented Dec 7, 2018 at 12:56
  • $\begingroup$ @chi your example does not explain why (a*|b*) does not match any b's . create is not in the language of (cre|ate) that's why it makes sense that it does not match create, it does match cre and ate, though. $\endgroup$
    – PascalIv
    Commented Dec 7, 2018 at 13:38
  • $\begingroup$ The tool you use finds matches, and does not directly consider the language of the regexp. If you use a as regexp, it will find a match within bab, even if bab is clearly not in the language of a. Using a regexp like (a*|zzz) will find a lot of matches using the empty string (in the language of a*), effectively ignoring the zzz part, as if the empty string "overlapped", as in the cre|rea example. Perhaps you can obtain what you want if you use as a regexp ^(a*|b*)$, marking the beginning and the end of the string explicitly with ^ and $ ? $\endgroup$
    – chi
    Commented Dec 7, 2018 at 14:00
  • $\begingroup$ I'm voting to close as off-topic, since this seems to be a question purely about a specific regular expression library. PascalIv, you're correct that, in CS, "or" is commutative. $\endgroup$ Commented Dec 7, 2018 at 14:05
  • $\begingroup$ @DavidRicherby Actually the question is not specific to a particular library or language. It is partly specific to this particular website, because the way it presents things is a bit confusing, but there's also a general concept at play: matching vs searching. So I'm voting to leave open. $\endgroup$ Commented Dec 7, 2018 at 20:22

1 Answer 1

2
$\begingroup$

It is not a bug; it is rather the JavaScript RegEx engine tries to match as much of the first of the two expressions combined by the "|" operator as it can. Thus, instead of matching a word like "bbb" with as many "b"s as possible, it matches the pattern a* against the empty word (implicitly) at the beginning of "bbb". Granted, the RegExr interface does not highlight this properly, but that is more of a missing feature than a bug.

As mentioned in the comments, you should also be aware the engine tries to find (possibly) strings in the input text which match the pattern specified by the regex; the matches are what are highlighted by the RegExr interface. This is a different use of regexes than in formal language theory, in which regexes are used to specify formal languages, and in which an input (word) as a whole either matches the regex or not.

Caveat: If you are trying regexes verbatim from a formal languages class, you may run into trouble when trying to specify the empty word; the character ε is not interpreted as the empty word but as the Greek lowercase epsilon character instead. This question on SE contains some ways of correctly specifying (only) the empty word.

Warning number 2: If you write L(a*|b*) verbatim for your expression there, it is interpreted as a capital $L$ followed by the pattern (a*|b*), not as the language corresponding to the pattern (a*|b*)!

$\endgroup$
3
  • $\begingroup$ Nice answer. It could be better if the ideas in @Chi's comment can be included. It could be better if you can make it explicit that "the tool" is one of most popular languages, JavaScript. $\endgroup$
    – John L.
    Commented Dec 7, 2018 at 19:14
  • $\begingroup$ No, the tool doesn't use sed syntax, it uses Javascript syntax (by default). And it does apply the * operator to the previous parenthesised group. $\endgroup$ Commented Dec 7, 2018 at 20:25
  • $\begingroup$ @Gilles @Apass.Jack Modified answer so as to refer directly to the JS engine. My (admittedly incorrect) remark on (a|b)* being invalid was partly due to the dubious documentation on the RegExr site, which says * matches "0 or more of the preceding token"; of course, it should read "preceding expression" instead. $\endgroup$
    – dkaeae
    Commented Dec 8, 2018 at 22:14

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.