Introduction

In computer science, regular expressions and glob patterns are used to specify sets of strings or paths. They are particularly useful for searching, matching, and manipulating text. A common question is whether two such patterns intersect, meaning whether there exists any string that matches both patterns. This article walks through an algorithmic approach based on automata theory to determine pattern intersection, with examples and complexity analysis.

Basics: Glob Patterns and Regular Expressions

Glob Patterns

Glob patterns are simplified, shell-style matching patterns primarily used for matching filenames or paths. Their wildcards include:

• *: Matches any number of any characters (including none).
• ?: Matches exactly one character.
• [abc]: Matches one character from the specified set.
• {a,b}: Matches any of the comma-separated sub-patterns.

Regular Expressions

Regular expressions (regex) are more powerful and expressive. Their core operators include:

• .: Matches any single character.
• *: Matches the preceding element zero or more times.
• +: Matches the preceding element one or more times.
• []: Denotes a character class.
• |: Alternation (logical OR between patterns).

Problem Statement

Given two patterns (glob or regex), determine whether there exists any string that matches both patterns simultaneously. Formally, given languages $L_1$ and $L_2$ defined by the two patterns, check whether $L_1 \cap L_2 \neq \emptyset$.

Algorithm Overview

The algorithm has four steps:

1. Conversion: Convert glob patterns to equivalent regular expressions if needed, since regex is strictly more expressive and subsumes glob semantics.
2. NFA Construction: Build a Non-deterministic Finite Automaton (NFA) for each pattern using Thompson's construction.
3. Product Automaton: Construct the product (intersection) automaton whose states are pairs from the two NFAs.
4. Emptiness Check: Search for any reachable accepting state in the product automaton. If one exists, the patterns intersect.

Detailed Steps

Step 1: Convert Globs to Regex

If the input is a glob pattern, convert it to an equivalent regex. Common translations:

For example, the glob *.txt becomes the regex ^.*\.txt$.

Step 2: Build NFAs

Use Thompson's construction to convert each regex into an NFA. Thompson's construction creates an NFA with $O(m)$ states for a regex of length $m$, where each operator (concatenation, union, Kleene star) maps to a small NFA fragment.

Step 3: Construct the Product Automaton

Given NFA $A$ with states $Q_A$ and NFA $B$ with states $Q_B$, the product automaton $P$ has states $Q_A \times Q_B$. A state $(p, q)$ in $P$ is an accepting state if and only if $p$ is accepting in $A$ and $q$ is accepting in $B$.

The transition function for the product automaton is:

$$\delta_P((p, q), a) = (\delta_A(p, a), \delta_B(q, a))$$

The product automaton can have up to $|Q_A| \times |Q_B|$ states, which is why this approach can be expensive for complex patterns.

Step 4: Check for Emptiness

Run a breadth-first or depth-first search from the initial state $(q_{0A}, q_{0B})$ of the product automaton. If any accepting state $(p, q)$ is reachable, then the two patterns have a non-empty intersection, and the path to that state reveals a witness string.

Complexity Analysis

• NFA Construction: $O(m)$ time and space per pattern, where $m$ is the pattern length.
• Product Automaton: Up to $O(|Q_A| \times |Q_B|)$ states. In the worst case this can be exponential if either NFA is large.
• Emptiness Check: Linear in the size of the product automaton, $O(|Q_A| \times |Q_B|)$.

For most practical glob patterns, the NFAs are small and this approach is efficient. For very complex regex patterns, the product automaton can become prohibitively large.

Practical Considerations

• Symbolic Automata: For patterns over large alphabets (like Unicode), symbolic automata represent transitions as predicates rather than individual characters, greatly reducing the state space.
• Approximate Methods: When exact intersection checking is too expensive, heuristic or SAT-based approaches can provide faster answers for common cases.
• Applications: File system search tools, CI/CD pipeline path filters, text editor search-and-replace, and language processing toolchains all benefit from intersection checking.

Summary Table

Conclusion

Determining whether two glob patterns or regular expressions intersect involves converting the problem into one of automata intersection and checking for reachable accept states. The product automaton construction is the core step, and its size is the main factor governing performance. For typical file-matching globs this approach is fast and practical. For complex regex patterns, symbolic automata or approximate methods may be needed.