2
$\begingroup$

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?
$\endgroup$

closed as off-topic by Emil Jeřábek supports Monica, Radu GRIGore, Aryeh, Lev Reyzin Jun 28 '17 at 20:35

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Emil Jeřábek supports Monica, Radu GRIGore, Aryeh, Lev Reyzin
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 4
    $\begingroup$ This is not a research-level question. Hint: regular languages are closed under intersection. $\endgroup$ – Emil Jeřábek supports Monica 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