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

<pre><code>Fo*bar and Fo+bar
</code></pre>

<p>More specifically:</p>

<ol>
<li>if $R_1$ and $R_2$ are two regular languages</li>
<li>can one determine if $R_1 \cap R_2 = \varnothing$ ?</li>
<li>And if one can what algorithms / methods can perform such a determination?</li>
<li>And are these algorithms / method NP hard?</li>
</ol>

CC BY-SA 3.0
2017-06-28T18:54:56.227Z
This is not a research-level question. Hint: regular languages are closed under intersection.
Emil Jeřábek
CC BY-SA 3.0
2017-06-29T04:36:18.820Z
@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
CC BY-SA 3.0
2017-06-29T07:54:51.937Z
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
CC BY-SA 3.0
2017-06-29T07:55:45.780Z
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
CC BY-SA 3.0
2017-06-29T07:57:46.827Z
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
CC BY-SA 3.0
2017-06-29T08:00:29.037Z
If we could solve this problem in $n^{2-\varepsilon}$ time for some positive $\varepsilon$, then we would get faster algorithms for SAT and other problems.
Michael Wehar
CC BY-SA 3.0
2017-06-29T08:01:29.320Z
There are some simple classes of regular expressions where we can solve it in $n^{2-\varepsilon}$ time.  Please feel free to message me anytime about this or related problems.  :)
Michael Wehar
CC BY-SA 3.0
2017-06-29T08:08:57.893Z
In computer software, the term regular expression often refers to something more complex than the basic theoretical notion.  For example, take a look at the Java Pattern class with its documentation: https://docs.oracle.com/javase/7/docs/api/java/util/regex/Pattern.html
Michael Wehar
CC BY-SA 3.0
2017-06-29T08:09:44.080Z
This relates to some of the theoretical notions of extended regular expressions.  For some classes of extended regular expressions, the intersection problem is much harder.
Michael Wehar
CC BY-SA 3.0
2017-06-29T08:13:20.287Z
In other words, solving the intersection problem in practice for software developers can be a bit more complex.  I met a few people who put some thought into this.  :)
Michael Wehar
<regular-expressions>
Have people explored the problem of regular expressions being matchable?
user1172468
# Have people explored the problem of regular expressions being matchable?

(Asked by: username_0 on 2017-06-28)

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:

if $R_1$ and $R_2$ are two regular languages
can one determine if $R_1 \cap R_2 = \varnothing$ ?
And if one can what algorithms / methods can perform such a determination?
And are these algorithms / method NP hard?

**Tags:** regular-expressions
> **Comments:**
> **username_1**: This is not a research-level question. Hint: regular languages are closed under intersection.  
> **username_0**: @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  
> **username_2**: 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.  
> **username_2**: 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.  
> **username_2**: 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.  
> **username_2**: If we could solve this problem in $n^{2-\varepsilon}$ time for some positive $\varepsilon$, then we would get faster algorithms for SAT and other problems.  
> **username_2**: There are some simple classes of regular expressions where we can solve it in $n^{2-\varepsilon}$ time.  Please feel free to message me anytime about this or related problems.  :)  
> **username_2**: In computer software, the term regular expression often refers to something more complex than the basic theoretical notion.  For example, take a look at the Java Pattern class with its documentation: https://docs.oracle.com/javase/7/docs/api/java/util/regex/Pattern.html  
> **username_2**: This relates to some of the theoretical notions of extended regular expressions.  For some classes of extended regular expressions, the intersection problem is much harder.  
> **username_2**: In other words, solving the intersection problem in practice for software developers can be a bit more complex.  I met a few people who put some thought into this.  :)  

---

## 0 answers

