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?
  • 4
    $\begingroup$ This is not a research-level question. Hint: regular languages are closed under intersection. $\endgroup$ – Emil Jeřábek Jun 28 '17 at 18:54
  • 1
    $\begingroup$ @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 $\endgroup$ – user1172468 Jun 29 '17 at 4:36
  • 1
    $\begingroup$ 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. $\endgroup$ – Michael Wehar Jun 29 '17 at 7:54
  • 1
    $\begingroup$ 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. $\endgroup$ – Michael Wehar Jun 29 '17 at 7:55
  • 2
    $\begingroup$ 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. $\endgroup$ – Michael Wehar Jun 29 '17 at 7:57