1

From theoretical computer science we know that the problem of determining whether a regular language is empty is decidable.

Is there a way to check whether a Java regular expression denotes the empty language, or in other words, whether no string exists that matches it?

Note that I'm NOT asking whether a regular expression exists that matches nothing nor what such a regular expression is. I know that there are, and that they are infinite. I'm asking how do I recognize them.

Pietro Braione
  • 1,123
  • 8
  • 22
  • 2
    Java's regular expressions (and a lot of REs in other languages as well) are not academic regular expressions - they are superset and are much more powerful. E.g. they have lookaheads and backreferences which make languages described by regexps non-regular. – yeputons May 11 '16 at 15:24
  • I might be wrong (I'm rusty on this topic), but since, as @yeputons said, Java's so-called "regular expressions" are in fact [neither regular nor context-free](https://en.wikipedia.org/wiki/Regular_expression#Patterns_for_non-regular_languages), they are undecidable. I believe their undecidability makes the answer to your question "No, it's not possible." – Jordan Running May 11 '16 at 16:37

0 Answers0