Introduction

Regular expressions (regex) are powerful tools for matching patterns in strings. However, determining if two regular expressions overlap, meaning whether there is at least one string that both expressions can match, is a non-trivial problem. Understanding how to detect overlap can be crucial in applications such as optimizing search algorithms, designing input validation systems, or detecting ambiguity in routing rules. This article explains the methods for detecting overlapping patterns between regexes through examples and technical analysis.

Defining Overlapping Expressions

Two regular expressions are said to overlap if there exists at least one string that both regexes can match. For example, the regex a.*b and .*ab overlap because the string "ab" matches both. In formal terms, two regexes R1 and R2 overlap when the intersection of their languages is non-empty: $L(R1) \cap L(R2) \neq \emptyset$.

Methods to Detect Overlap

1. Constructing a Product Automaton

Both deterministic (DFA) and non-deterministic finite automata (NFA) can represent regular expressions. The most rigorous approach constructs a product automaton from two regex-derived automata:

Step 1: Convert each regex to an NFA using Thompson's construction algorithm. Each regex becomes a state machine with transitions on input characters.

Step 2: Build the product automaton. Create a new automaton where each state is a pair $(q_i, q_j)$ drawn from the states of the two NFAs. A transition exists on character $c$ from $(q_i, q_j)$ to $(q_i', q_j')$ if and only if both original NFAs have transitions on $c$ from $q_i$ to $q_i'$ and from $q_j$ to $q_j'$ respectively.

Step 3: Check for an accepting state. If any state $(q_i, q_j)$ in the product automaton is reachable from the start state and both $q_i$ and $q_j$ are accepting states in their respective NFAs, then the regexes overlap. You can find this using a simple BFS or DFS from the start state.

The product automaton approach is complete and correct for all regular languages. Its downside is that converting an NFA to a DFA can cause an exponential blowup in the number of states (a regex with $n$ states can produce a DFA with up to $2^n$ states).

2. Using SAT/SMT Solvers

Modern SAT (Boolean Satisfiability) or SMT (Satisfiability Modulo Theories) solvers can decide regex overlap by encoding the problem into a logical formula:

• Encode constraints: Translate each regex into a set of logical constraints capturing their match requirements over a bounded string length.
• Solve for intersection: Use the solver to test if there exists a string assignment that satisfies both sets of constraints simultaneously.

Tools like Z3 have built-in support for regex constraints, making this approach practical:

1from z3 import *
2
3s = Solver()
4x = String('x')
5s.add(InRe(x, Re("a.*b")))
6s.add(InRe(x, Re(".*ab")))
7
8if s.check() == sat:
9    print("Overlap found:", s.model()[x])
10else:
11    print("No overlap")

3. Syntax Tree Simplification

For simpler regexes, you can analyze and simplify their syntax trees to detect obvious overlaps without constructing full automata:

• Parse each regex into a syntax tree.
• Identify common sub-expressions (shared character classes, shared literal prefixes or suffixes).
• If a common sub-expression can generate at least one string, the regexes overlap.

This approach is fast but incomplete. It works well as a quick pre-check before falling back to a more expensive method.

Worked Example

Consider regexes R1 = a*b+ and R2 = ab*.

Using the product automaton approach:

1. R1 accepts strings with zero or more "a" characters followed by one or more "b" characters (e.g., "b", "ab", "aabb").
2. R2 accepts strings starting with exactly one "a" followed by zero or more "b" characters (e.g., "a", "ab", "abbb").
3. The intersection includes "ab", "abb", "abbb", and so on. Any string matching ab+ is accepted by both.

Using Z3:

Encoding both constraints and running the solver confirms that "ab" satisfies both, proving overlap.

Complexity Considerations

Practical Tips

• Pre-evaluation: Before running expensive algorithms, check for trivial overlaps. If both regexes accept the empty string, they overlap. If both contain a common literal substring, they likely overlap.
• Pattern pruning: Simplify regexes by removing redundant quantifiers or character classes before analysis. This reduces automaton size.
• Bounded checking: In many practical applications, you only care about overlaps for strings up to a certain length. Bounding the string length makes the SMT approach much faster.

Summary

Detecting whether two regular expressions overlap requires determining if the intersection of their languages is non-empty. The product automaton method is theoretically sound but can be expensive. SAT/SMT solvers provide a practical alternative with tool support. For simple cases, syntax tree analysis offers a fast heuristic. The right approach depends on your regex complexity and whether you need guaranteed completeness or just a quick check.