# Have people explored the problem of regular expressions being matchable? [closed]

I ran into a problem of determining if two regular expressions would have any possible matches in common. For example:

Fo*bar and Fo+bar


More specifically:

1. if $R_1$ and $R_2$ are two regular languages
2. can one determine if $R_1 \cap R_2 = \varnothing$ ?
3. And if one can what algorithms / methods can perform such a determination?
4. And are these algorithms / method NP hard?
• This is not a research-level question. Hint: regular languages are closed under intersection. – Emil Jeřábek Jun 28 '17 at 18:54
• @EmilJeřábek -- thank you for the hint -- I guess my questions was that even if the intersection is closed -- is it determinable if the intersection is the null set of not. Not sure if your hint answers this question -- I reformulated the question -- thanks – user1172468 Jun 29 '17 at 4:36
• Determining whether or not two regular languages have a non-empty intersection is a research-level problem that I've dedicated several years studying. There are many different variants to this problem depending on how the regular languages are represented. – Michael Wehar Jun 29 '17 at 7:54
• In your case, your considering the problem where you're given two regular expressions and you want to determine if their corresponding regular languages have a non-empty intersection. – Michael Wehar Jun 29 '17 at 7:55
• If $n$ denotes the length (in terms of number of characters) of the regular expressions, then we should be able to solve the problem in roughly $n^2$ time. First, you convert the regular expressions to NFA's. Then, you apply the product construction to the NFA's. Then, you check if there exists a path from the product start state to the product final state in the product NFA's state diagram. If there exists such a path, then the intersection is non-empty. If there does not, then the intersection is empty. – Michael Wehar Jun 29 '17 at 7:57