<p>While regex size blows up when defining a function that take two regexes, and return one regex representing their complement/intersection (see <a href="https://arxiv.org/abs/0802.2869" rel="noreferrer">Succinctness of the Complement and Intersection of Regular Expressions</a>), in reality regular expression engine compile regexes into finite automata. Complement and Intersection in finite automata is trivial and do not blow up the size too much, so why don't engines support them?</p>

<parsing><regex>
Why don't popular regex engines support complement and intersection?
CC BY-SA 4.0
2023-12-22T11:08:46.897Z
Can you give an example of what this would mean in concrete terms? Are you imagining some syntax that allows you to specify two sub-patterns, and a relationship between them? Or, a function in the host language which takes two regex objects and combines them in a way not supported by the string syntax? The only language I can think of that approaches the latter is Raku whose "rules" (deliberately not named as regular expressions) can be nested without first converting back to a string representation.
IMSoP
CC BY-SA 4.0
2023-12-22T11:57:47.930Z
They are supported as negative and positive lookaheads.
user23013
CC BY-SA 4.0
2023-12-22T17:39:44.213Z
I'm tempted to write an answer based on the observation that the string searching systems known as "regexes" have only a historical link to the theory of "regular expressions", but I don't know enough about the latter to write it confidently. In particular, I don't actually know what "complement and intersection" mean in context, but I strongly suspect the reason they're not directly supported in regexes is that they're meaningless - that is, "which part of this string matches the complement of this pattern?" doesn't have a sensible answer.
IMSoP
CC BY-SA 4.0
2023-12-22T19:44:52.710Z
@IMSoP Complement and intersection refer to sets of strings included in a language (i.e. the set of strings matched by a regex). Each regex defines a set of strings it matches, the complement of that set is all strings not matched, and then you could look for a regex which matches that set ─ or, if your regex syntax allows for negation then you can directly transform the original regex into a regex which matches the complement.
kaya3
CC BY-SA 4.0
2023-12-22T19:48:53.993Z
At least in Rust's [`regex` crate](https://docs.rs/regex/1.10.2/regex/), [there are no plans for complement or conjunction due to it not having enough use cases](https://github.com/rust-lang/regex/discussions/837). However the crate exposes [`regex-syntax`](https://crates.io/crates/regex-syntax/0.8.2) and [`regex-automata`](https://docs.rs/regex-automata/0.4.3/regex_automata/), and `regex-automata` contains methods for [intersection and subtraction](https://docs.rs/regex-automata/0.4.3/regex_automata/util/look/struct.LookSet.html), so it's not too hard to implement on your own.
tarzh
CC BY-SA 4.0
2023-12-22T20:56:05.553Z
@kaya3 Right, so the disconnect is that in practice "regexes" (to use Larry Wall's suggestion of a deliberate contrast from "regular expressions") are not used to "define sets of strings", they're used to perform an assertion or a modification on a particular input. They are also used in the context of a host language, so if you want to say "A does not match pattern X", you can generally write "not (A matches pattern X)" rather than needing syntax for "A matches pattern (not X)"
IMSoP
CC BY-SA 4.0
2023-12-22T21:26:16.657Z
@IMSoP I think this is missing the point; intersection of one expression with the complement of another *is* a useful operation, and it *is* supported entirely within Perl's regexes, as has already been pointed out.
Michael Homer
CC BY-SA 4.0
2023-12-22T22:08:28.127Z
@IMSoP I am thinking along the line of "a new unary/binary operator in regex language", not necessarily implement via 'old regex to old regex function', as that blow up quick.
Marisa Kirisame
CC BY-SA 4.0
2023-12-23T06:05:19.847Z
"*regular expression engine compile regex onto finite automata*" - many (most?) actually don't, they use backtracking.
Bergi
CC BY-SA 4.0
2023-12-24T23:19:36.023Z
Hi people, I found all 4 answer instructive, and do not know which one to accept. Do I have to pick one? I want to just leave it be.
Marisa Kirisame
CC BY-SA 4.0
2023-12-25T08:15:45.197Z
It’s not mandatory to accept an answer, and actually it’s quite common on this site (maybe more than others on the network) to skip that. It’s fine to leave it as-is if you prefer, or to pick one, it’s entirely up to you.
Michael Homer
CC BY-SA 4.0
2023-12-25T08:37:49.467Z
@MichaelHomer thanks, I will leave it as is.
Marisa Kirisame
CC BY-SA 4.0
2023-12-25T15:32:28.443Z
What would you use it for, and are you sure it is the right hammer to do it with?
Thorbjørn Ravn Andersen
<p>For a reasonable definition of &quot;efficient&quot;, it is impossible to build an efficient RE matching engine which handles &quot;negative&quot; expressions.</p>
<p>Specifically, something has to give; either the match will be inefficient (in the sense of consuming more input than it has to) or the representation of the automaton will be inefficient (in the sense of being exponentially larger than the input RE) in the general case.</p>
<p>But first, some intuition. Consider a regular expression over the alphabet <span class="math-container">$ab$</span> that matches all strings that don't contain <span class="math-container">$aa$</span>.</p>
<p><span class="math-container">$$L = (a|b)^* \setminus (a|b)^*\,aa\,(a|b)^*$$</span></p>
<p>An efficient (in the above sense) implementation of this should stop matching as soon as the first <span class="math-container">$aa$</span> is found. However, any automaton that is based on some kind of recursive decomposition of the structure of the RE alone will not do this, because this RE has the form <span class="math-container">$L = L_1 \setminus L_2$</span>, where both <span class="math-container">$L_1$</span> and <span class="math-container">$L_2$</span> match the <em>entire</em> length of the string.</p>
<p>So, you might reason, why not use a DFA. Well, there's a problem with that, too. The minimal DFA can be <em>exponentially</em> larger than the smallest RE or NFA for the same language.</p>
<p>A classic example is:</p>
<p><span class="math-container">$$L_n = (0 | 1)^*\,1\,(0 | 1)^n$$</span></p>
<p>It's easy to construct a NFA for <span class="math-container">$L_n$</span> with <span class="math-container">$n+1$</span> states, but the minimal DFA must have at least <span class="math-container">$2^n$</span> states.</p>
<p>This is one reason why library regular expression engines rarely use DFAs, let alone minimal ones.</p>
<p>But I claimed at the top that it was impossible.</p>
<p>Consider the language:</p>
<p><span class="math-container">$$N = L_a \setminus L_b$$</span></p>
<p>where <span class="math-container">$L_a$</span> and <span class="math-container">$L_b$</span> are different REs that represent the <em>same</em> language. If we think that an efficient matching algorithm should know that it doesn't need to examine any input at all, then this is the same as the problem of deciding that two REs are equivalent.</p>
<p>And that problem is known to be PSPACE-complete.</p>

CC BY-SA 4.0
2023-12-23T05:33:19.633Z
2023-12-23T05:33:19.633Z
Pseudonym
CC BY-SA 4.0
2023-12-23T18:18:03.677Z
I think this is too strong and the final example a bit trite; reducing to a minimal DFA is the expensive operation, but before that there was a perfectly fine intersection+complement DFA with a perfectly fine linear time in the input. Requiring that it reduce to the reject automaton in order to be “efficient” also means that every backtracking engine is not “efficient”, but then what does this show except a toy mathematical property? Clearly in terms of this question engines are not required to consume minimal input or there wouldn’t have been any “popular” ones to be inadequate to start with.
Michael Homer
CC BY-SA 4.0
2023-12-23T23:44:17.273Z
Just to be clear, it's subexpressions that are in a "negative" position (in this case, on the right-hand-side of set difference) that result in over-consumption. REs with only subexpressions in "positive" positions do not have this property. POSIX regexes do not have this property. Extended regex engines such as PCRE require exponential time and significant backtracking in the worst case, so clearly some have decided it's worth it. And I didn't mention substring capture at all.
Pseudonym
CC BY-SA 4.0
2023-12-23T23:53:23.400Z
You're right that intersection/complement/difference can be solved in quadratic time, but importantly, this is quadratic time per operator, and it's quadratic in the size of the DFAs and not the size of the REs. That's why I noted that the minimal DFA for some REs have exponential size.
Pseudonym
CC BY-SA 4.0
2023-12-25T12:52:32.490Z
@user253751 That regular expression matches all strings that have a 1 in the $n$th-last place. A DFA that matches it therefore needs to have $n$ symbols of "memory", i.e. $2^n$ states. Another way to convince yourself is to construct a DFA for some $n$, and the fact that minimal DFAs are unique.
Pseudonym
<p>A succinct explanation lies in the historical development of regular expression engines. When Ken Thompson initially implemented a regular expression engine in his QED text editor, he opted for a well-established syntax known as the &quot;regular language,&quot; which, at that time, did not include complement and intersection operations. Subsequently, this syntax crystallized into what is now recognized as POSIX regular expression syntax.
The advent of Perl introduced an alternative Perl-style regular expression syntax, representing a substantial expansion within the same framework. Perl-style regex brought features such as lookahead, imbuing a certain degree of &quot;control-flow&quot; style. An ideal implementation of a regular expression engine based on the Perl-style syntax has functionally encompassed the descriptions of intersection and complement found in classical set-theoretic languages. The latter, as separate entities, became deemed unnecessary within this feature set.</p>
<p>In other words, when we refer to the &quot;regular expression syntax processed by a regex engine,&quot; we are typically alluding to two distinct sets of principles. Firstly, there is the classical regular expression syntax inherited by POSIX, originating from Ken Thompson's original implementation. This classical syntax closely adheres to Kleene's classic regular grammar, eschewing concepts such as intersection and complement. Secondly, we have the &quot;modern regular expression syntax&quot; epitomized by PCRE (Perl Compatible Regular Expressions). While sharing a common name with the former, they have evolved into two separate entities, which has the modern solution, dispenses with the need for further application of set theory language.</p>

CC BY-SA 4.0
2023-12-22T11:25:33.343Z
2023-12-22T12:42:22.637Z
2023-12-22T12:42:22.637Z
Camille Dolma
CC BY-SA 4.0
2023-12-22T13:21:26.097Z
A relevant quote from Larry Wall in the design documents for Perl 6 (what is now Raku): "We now try to call them regex rather than 'regular expressions' because they haven't been regular expressions for a long time". In other words, the CS theory of regular expressions and the practical implementation of string matching languages diverged some time ago.
IMSoP
CC BY-SA 4.0
2023-12-22T18:38:11.033Z
@IMSoP Occasionally questions about CS regular expressions pop up on SO, I tell them to ask on [cs.se] because they're so far from what actual programmers deal with.
Barmar
CC BY-SA 4.0
2023-12-22T18:40:37.360Z
It should also be noted that many of the features of PCRE and other modern regexp flavors make it difficult to translate them to finite automata. So theories about combining FA don't really apply.
Barmar
<p><strong>TLDR:</strong> Doing complementation and intersection on automata is hard. There may or may not be other ways to support these features in an indirect way</p>
<hr />
<p>There are two broad categories of algorithms for matching regular expressions: <strong>backtracking</strong> engines and <strong>automata-based</strong> engines.</p>
<blockquote>
<p>in reality regular expression engine compile regexes into finite automata.</p>
</blockquote>
<p>This is arguably incorrect. A large number of the regular expression libraries included with popular programming languages including Python, Java, Javascript and libraries like PCRE are based on backtracking. There are relatively few regular expression engines which are based on automata. Notable examples include RE2 and Hyperscan.</p>
<p>Backtracking is exponentially slow in the worst case. However, in practice, regular expressions are frequently used for simple text-processing tasks in which case the performance of these engines are not so bad. I suspect the main reason that backtracking is used so widely in practice is because it is easy to implement, and the implementations are very flexible, allowing the addition of non-classical features like lookarounds (shameless plug for <a href="https://kmamouras.github.io/papers/regex-lookaround-draft-POPL%2724.pdf" rel="noreferrer">my POPL paper</a>), capture groups, backreferences, etc.</p>
<p>How badly will backtracking be affected if negation and intersection were added? I am not sure.</p>
<hr />
<p>Generally, the automata based algorithms would be based on <strong>Non-Deterministic</strong> Finite Automata (NFA). This is because the corresponding deterministic automata would often be too large.</p>
<p>It is possible to simulate/run an NFA in <span class="math-container">$O(m^2 \cdot n)$</span> time (where <span class="math-container">$m$</span> is the size of the NFA and <span class="math-container">$n$</span> is the size of the string. If implemented carefully, it is possible to construct an NFA from a regex of size <span class="math-container">$r$</span> and simulate the regex in <span class="math-container">$O(r \cdot n)$</span> time.</p>
<blockquote>
<p><strong>Intersection</strong> in finite automata is trivial and do not blow up the size too much</p>
</blockquote>
<p>Let's examine that claim. The textbook algorithm for constructing the intersection automaton for an automaton of size <span class="math-container">$a$</span> and another of size <span class="math-container">$b$</span> would produce an automaton of size <span class="math-container">$a \times b$</span>. Thus, if you have <span class="math-container">$k$</span> regular expressions whose intersection you want to consider <span class="math-container">$r_1 \cap r_2 \cdots r_k$</span>, then you will create an automaton of size <span class="math-container">$r_1 \times \cdots \times r_k$</span>. This 'trivial' algorithm thus results in an exponentially large Automaton.</p>
<p><a href="https://vmahesh.cs.illinois.edu/papers/rta03.pdf" rel="noreferrer">Rosu and Vishwanathan</a> in their paper &quot;Testing Extended Regular Language Membership Incrementally by Rewriting&quot; have a proof of the following claim (See Theorem 1): Suppose algorithm <span class="math-container">$A$</span> scans a string from left to right whilst producing judgements at each step about whether the string so far matches a given regex potentially with intersection. Then, <span class="math-container">$A$</span> must store at least <span class="math-container">$O(2^{c\sqrt{r}})$</span> bits.</p>
<hr />
<p><strong>Complementation</strong> is harder. Complementing Deterministic Automata is easy. Complementing NFAs is not.</p>
<p>To complement an NFA, you <em>cannot</em> simply swap the accepting and non-accepting states. This is because, in order to demonstrate that <span class="math-container">$w \not \in L$</span>, you need to show that <em>all</em> paths do not accept the string. The most trivial algorithm for complementation will involve determinization of the automaton first.</p>
<p>This means that if you have a regular expression with multiple negations inside it, you must incur an exponential cost to determinize each of them! So, with negation, the NFAs that you get are worse than any tower of exponentials. Indeed, it is known that for regular expressions with complementation, the NFAs may have <a href="https://en.wikipedia.org/wiki/Nonelementary_problem" rel="noreferrer"><strong>non-elementary</strong></a> size.</p>
<hr />
<p>Many of these lowerbound results only applies to streaming algorithms. So, it is possible that there are certain algorithms which make multiple passes on the string to match the regex which works much better. Indeed, <a href="https://link.springer.com/chapter/10.1007/978-3-540-71389-0_24" rel="noreferrer">this</a> paper from Rosu titled &quot;An Effective Algorithm for the Membership Problem for Extended Regular Expressions&quot; seems to be able to tackle this problem in polynomial time (even with complementation!). However, as far as I know this algorithm has never been implemented.</p>
<p>There seems to be <a href="https://www.microsoft.com/en-us/research/uploads/prod/2020/08/pldi21-SBFA-final.pdf" rel="noreferrer">some</a> <a href="https://www.microsoft.com/en-us/research/uploads/prod/2019/02/SRM_tacas19.pdf" rel="noreferrer">recent</a> research involving derivatives which seem to suggest that you can build practical regular expression engines with intersection. I am not certain how solid their theoretical guarantees are.</p>
<p>It appears to be the case that the regular expression fragment of logics used for assertions by hardware designers like <a href="https://en.wikipedia.org/wiki/Property_Specification_Language" rel="noreferrer">PSL</a> or <a href="https://en.wikipedia.org/wiki/SystemVerilog#Assertions" rel="noreferrer">SVA</a> do support intersection. It is unclear to me however, how well these features are supported in implementaions.</p>

CC BY-SA 4.0
2023-12-23T18:42:55.273Z
2023-12-23T18:42:55.273Z
Agnishom Chattopadhyay
CC BY-SA 4.0
2023-12-23T23:22:12.787Z
Nice! I thought RE got compiled to DFA via Thompson algorithm, which is my key misunderstanding.
Marisa Kirisame
<p>There are few &quot;popular&quot; regex dialects today that truly implement the regular languages; POSIX BREs are probably the most widespread such form due to standardisation. Most libraries instead represent some non-regular extension with elements that have been found useful in practice, most trivially by including backreferences.</p>
<p>The criterion of popularity is somewhat self-reinforcing here — <strong>people want to use those features, so the libraries that don't have them aren't <em>popular</em></strong>. For the engines that <em>do</em> have them, this non-regularity has a couple of relevant flow-on effects.</p>
<ol>
<li><p>The languages identified by these expressions no longer have simple complementation or intersection transformations.</p>
<p>Any regular language is accepted by a DFA, and constructing the intersecting NFA of two DFAs is fairly trivial, although it does have potentially exponential state blowout in the process. Constructing the complementary one is a bit more complex, but doable. Intersecting two pushdown automata is much harder, and the most practical way to complement one is realistically just to run it and invert the result, which brings us to...</p>
</li>
<li><p>Some of the other features added largely replicate the utility of intersection and complement operations, while supporting other uses too.</p>
<p><a href="https://perldoc.perl.org/perlre#Lookaround-Assertions" rel="noreferrer">Perl</a>, <a href="https://pcre2project.github.io/pcre2/doc/html/pcre2syntax.html#SEC22" rel="noreferrer">PCRE</a>, <a href="https://learn.microsoft.com/en-us/dotnet/standard/base-types/regular-expression-language-quick-reference#grouping-constructs" rel="noreferrer">.NET regular expressions</a>, and other common matching engines include support for zero-width positive lookahead assertions (generally <code>(?=xyz)</code>), which replicate the matching effects of intersection: <a href="https://michael.homer.nz/Tools/Regex/#(a%7Cb)+&amp;(b%7Cc)+%7Ebc" rel="noreferrer"><code>(a|b)+&amp;(b|c)+</code></a> matches the same inputs as <code>(?=(b|c)+)(a|b)</code>. Practical applications of intersection are generally of this form, with a &quot;covering&quot; language and some separately-described acceptance criteria, so the utility of intersection functionality is largely covered.</p>
<p>They  also generally support <em>negative</em> lookahead (and lookbehind) expressions, typically <code>(?!xyz)</code>; these allow a match only when the expression inside <em>does not</em> match at that point, which is similar but not quite identical to complement. Practical applications of complement are <em>usually</em> going to be of the form complement-and-intersect, which is what happens here</p>
<p>Both of these don't impose structural restrictions on the matching system: it's possible to ignore them entirely for a first pass and then validate any assertions by running another match at that point when the rest of the pattern has matched, and it's also possible to optimise them into DFA intersections when that's worthwhile and achievable.</p>
</li>
</ol>
<p>There <em>is</em> potential value in supporting intersection and complementation operations directly in some contexts, where the guaranteed linear-time matching provided by a DFA is valuable. This could be the case for use in public systems where the expressions are user-provided, for example. However, those are application-specific use cases, and language-level support will generally be more broadly-focused; outside libraries to support those use cases do exist, but are &quot;popular&quot; only in the niches where that usage is important.</p>
<p>When you need to be able to do that, you use one of the libraries that supports it, and when you don't, you probably use the regex system that came with your language, or one of the general-purpose libraries with broad functionality and plenty of recommendations, documentation, and past experience. The latter default choices are the ones that are popular, which also drives investment in optimisation work and yet further extensions, making them an even better default choice and more popular.</p>

CC BY-SA 4.0
2023-12-22T21:45:32.787Z
2023-12-22T21:45:32.787Z
Michael Homer
# Why don't popular regex engines support complement and intersection?
Posted by: username_0 on 2023-12-22
While regex size blows up when defining a function that take two regexes, and return one regex representing their complement/intersection (see [Succinctness of the Complement and Intersection of Regular Expressions](https://arxiv.org/abs/0802.2869)), in reality regular expression engine compile regexes into finite automata. Complement and Intersection in finite automata is trivial and do not blow up the size too much, so why don't engines support them?
**Tags:** parsing regex
> **Comments:**
> **username_1**: Can you give an example of what this would mean in concrete terms? Are you imagining some syntax that allows you to specify two sub-patterns, and a relationship between them? Or, a function in the host language which takes two regex objects and combines them in a way not supported by the string syntax? The only language I can think of that approaches the latter is Raku whose "rules" (deliberately not named as regular expressions) can be nested without first converting back to a string representation.  
> **username_2**: They are supported as negative and positive lookaheads.  
> **username_1**: I'm tempted to write an answer based on the observation that the string searching systems known as "regexes" have only a historical link to the theory of "regular expressions", but I don't know enough about the latter to write it confidently. In particular, I don't actually know what "complement and intersection" mean in context, but I strongly suspect the reason they're not directly supported in regexes is that they're meaningless - that is, "which part of this string matches the complement of this pattern?" doesn't have a sensible answer.  
> **username_3**: @IMSoP Complement and intersection refer to sets of strings included in a language (i.e. the set of strings matched by a regex). Each regex defines a set of strings it matches, the complement of that set is all strings not matched, and then you could look for a regex which matches that set ─ or, if your regex syntax allows for negation then you can directly transform the original regex into a regex which matches the complement.  
> **username_4**: At least in Rust's [`regex` crate](https://docs.rs/regex/1.10.2/regex/), [there are no plans for complement or conjunction due to it not having enough use cases](https://github.com/rust-lang/regex/discussions/837). However the crate exposes [`regex-syntax`](https://crates.io/crates/regex-syntax/0.8.2) and [`regex-automata`](https://docs.rs/regex-automata/0.4.3/regex_automata/), and `regex-automata` contains methods for [intersection and subtraction](https://docs.rs/regex-automata/0.4.3/regex_automata/util/look/struct.LookSet.html), so it's not too hard to implement on your own.  
> **username_1**: @kaya3 Right, so the disconnect is that in practice "regexes" (to use Larry Wall's suggestion of a deliberate contrast from "regular expressions") are not used to "define sets of strings", they're used to perform an assertion or a modification on a particular input. They are also used in the context of a host language, so if you want to say "A does not match pattern X", you can generally write "not (A matches pattern X)" rather than needing syntax for "A matches pattern (not X)"  
> **username_5**: @IMSoP I think this is missing the point; intersection of one expression with the complement of another *is* a useful operation, and it *is* supported entirely within Perl's regexes, as has already been pointed out.  
> **username_0**: @IMSoP I am thinking along the line of "a new unary/binary operator in regex language", not necessarily implement via 'old regex to old regex function', as that blow up quick.  
> **username_6**: "*regular expression engine compile regex onto finite automata*" - many (most?) actually don't, they use backtracking.  
> **username_0**: Hi people, I found all 4 answer instructive, and do not know which one to accept. Do I have to pick one? I want to just leave it be.  
> **username_5**: It’s not mandatory to accept an answer, and actually it’s quite common on this site (maybe more than others on the network) to skip that. It’s fine to leave it as-is if you prefer, or to pick one, it’s entirely up to you.  
> **username_0**: @MichaelHomer thanks, I will leave it as is.  
> **username_7**: What would you use it for, and are you sure it is the right hammer to do it with?  
---
## 4 answers
### Answer by username_9 on 2023-12-22. Score: 16
A succinct explanation lies in the historical development of regular expression engines. When Ken Thompson initially implemented a regular expression engine in his QED text editor, he opted for a well-established syntax known as the "regular language," which, at that time, did not include complement and intersection operations. Subsequently, this syntax crystallized into what is now recognized as POSIX regular expression syntax.
The advent of Perl introduced an alternative Perl-style regular expression syntax, representing a substantial expansion within the same framework. Perl-style regex brought features such as lookahead, imbuing a certain degree of "control-flow" style. An ideal implementation of a regular expression engine based on the Perl-style syntax has functionally encompassed the descriptions of intersection and complement found in classical set-theoretic languages. The latter, as separate entities, became deemed unnecessary within this feature set.

In other words, when we refer to the "regular expression syntax processed by a regex engine," we are typically alluding to two distinct sets of principles. Firstly, there is the classical regular expression syntax inherited by POSIX, originating from Ken Thompson's original implementation. This classical syntax closely adheres to Kleene's classic regular grammar, eschewing concepts such as intersection and complement. Secondly, we have the "modern regular expression syntax" epitomized by PCRE (Perl Compatible Regular Expressions). While sharing a common name with the former, they have evolved into two separate entities, which has the modern solution, dispenses with the need for further application of set theory language.
> **Comments:**
> **username_1** (2023-12-22): A relevant quote from Larry Wall in the design documents for Perl 6 (what is now Raku): "We now try to call them regex rather than 'regular expressions' because they haven't been regular expressions for a long time". In other words, the CS theory of regular expressions and the practical implementation of string matching languages diverged some time ago.  
> **username_10** (2023-12-22): @IMSoP Occasionally questions about CS regular expressions pop up on SO, I tell them to ask on [cs.se] because they're so far from what actual programmers deal with.  
> **username_10** (2023-12-22): It should also be noted that many of the features of PCRE and other modern regexp flavors make it difficult to translate them to finite automata. So theories about combining FA don't really apply.  
---
### Answer by username_8 on 2023-12-23. Score: 12
For a reasonable definition of "efficient", it is impossible to build an efficient RE matching engine which handles "negative" expressions.

Specifically, something has to give; either the match will be inefficient (in the sense of consuming more input than it has to) or the representation of the automaton will be inefficient (in the sense of being exponentially larger than the input RE) in the general case.

But first, some intuition. Consider a regular expression over the alphabet $ab$ that matches all strings that don't contain $aa$.

$$L = (a|b)^\* \setminus (a|b)^\*\,aa\,(a|b)^\*$$

An efficient (in the above sense) implementation of this should stop matching as soon as the first $aa$ is found. However, any automaton that is based on some kind of recursive decomposition of the structure of the RE alone will not do this, because this RE has the form $L = L\_1 \setminus L\_2$, where both $L\_1$ and $L\_2$ match the *entire* length of the string.

So, you might reason, why not use a DFA. Well, there's a problem with that, too. The minimal DFA can be *exponentially* larger than the smallest RE or NFA for the same language.

A classic example is:

$$L\_n = (0 | 1)^\*\,1\,(0 | 1)^n$$

It's easy to construct a NFA for $L\_n$ with $n+1$ states, but the minimal DFA must have at least $2^n$ states.

This is one reason why library regular expression engines rarely use DFAs, let alone minimal ones.

But I claimed at the top that it was impossible.

Consider the language:

$$N = L\_a \setminus L\_b$$

where $L\_a$ and $L\_b$ are different REs that represent the *same* language. If we think that an efficient matching algorithm should know that it doesn't need to examine any input at all, then this is the same as the problem of deciding that two REs are equivalent.

And that problem is known to be PSPACE-complete.
> **Comments:**
> **username_5** (2023-12-23): I think this is too strong and the final example a bit trite; reducing to a minimal DFA is the expensive operation, but before that there was a perfectly fine intersection+complement DFA with a perfectly fine linear time in the input. Requiring that it reduce to the reject automaton in order to be “efficient” also means that every backtracking engine is not “efficient”, but then what does this show except a toy mathematical property? Clearly in terms of this question engines are not required to consume minimal input or there wouldn’t have been any “popular” ones to be inadequate to start with.  
> **username_8** (2023-12-23): Just to be clear, it's subexpressions that are in a "negative" position (in this case, on the right-hand-side of set difference) that result in over-consumption. REs with only subexpressions in "positive" positions do not have this property. POSIX regexes do not have this property. Extended regex engines such as PCRE require exponential time and significant backtracking in the worst case, so clearly some have decided it's worth it. And I didn't mention substring capture at all.  
> **username_8** (2023-12-23): You're right that intersection/complement/difference can be solved in quadratic time, but importantly, this is quadratic time per operator, and it's quadratic in the size of the DFAs and not the size of the REs. That's why I noted that the minimal DFA for some REs have exponential size.  
> **username_8** (2023-12-25): @user253751 That regular expression matches all strings that have a 1 in the $n$th-last place. A DFA that matches it therefore needs to have $n$ symbols of "memory", i.e. $2^n$ states. Another way to convince yourself is to construct a DFA for some $n$, and the fact that minimal DFAs are unique.  
---
### Answer by username_5 on 2023-12-22. Score: 8
There are few "popular" regex dialects today that truly implement the regular languages; POSIX BREs are probably the most widespread such form due to standardisation. Most libraries instead represent some non-regular extension with elements that have been found useful in practice, most trivially by including backreferences.

The criterion of popularity is somewhat self-reinforcing here — **people want to use those features, so the libraries that don't have them aren't *popular***. For the engines that *do* have them, this non-regularity has a couple of relevant flow-on effects.

1. The languages identified by these expressions no longer have simple complementation or intersection transformations.

   Any regular language is accepted by a DFA, and constructing the intersecting NFA of two DFAs is fairly trivial, although it does have potentially exponential state blowout in the process. Constructing the complementary one is a bit more complex, but doable. Intersecting two pushdown automata is much harder, and the most practical way to complement one is realistically just to run it and invert the result, which brings us to...
2. Some of the other features added largely replicate the utility of intersection and complement operations, while supporting other uses too.

   [Perl](https://perldoc.perl.org/perlre#Lookaround-Assertions), [PCRE](https://pcre2project.github.io/pcre2/doc/html/pcre2syntax.html#SEC22), [.NET regular expressions](https://learn.microsoft.com/en-us/dotnet/standard/base-types/regular-expression-language-quick-reference#grouping-constructs), and other common matching engines include support for zero-width positive lookahead assertions (generally `(?=xyz)`), which replicate the matching effects of intersection: [`(a|b)+&(b|c)+`](https://michael.homer.nz/Tools/Regex/#(a%7Cb)+&(b%7Cc)+%7Ebc) matches the same inputs as `(?=(b|c)+)(a|b)`. Practical applications of intersection are generally of this form, with a "covering" language and some separately-described acceptance criteria, so the utility of intersection functionality is largely covered.

   They also generally support *negative* lookahead (and lookbehind) expressions, typically `(?!xyz)`; these allow a match only when the expression inside *does not* match at that point, which is similar but not quite identical to complement. Practical applications of complement are *usually* going to be of the form complement-and-intersect, which is what happens here

   Both of these don't impose structural restrictions on the matching system: it's possible to ignore them entirely for a first pass and then validate any assertions by running another match at that point when the rest of the pattern has matched, and it's also possible to optimise them into DFA intersections when that's worthwhile and achievable.

There *is* potential value in supporting intersection and complementation operations directly in some contexts, where the guaranteed linear-time matching provided by a DFA is valuable. This could be the case for use in public systems where the expressions are user-provided, for example. However, those are application-specific use cases, and language-level support will generally be more broadly-focused; outside libraries to support those use cases do exist, but are "popular" only in the niches where that usage is important.

When you need to be able to do that, you use one of the libraries that supports it, and when you don't, you probably use the regex system that came with your language, or one of the general-purpose libraries with broad functionality and plenty of recommendations, documentation, and past experience. The latter default choices are the ones that are popular, which also drives investment in optimisation work and yet further extensions, making them an even better default choice and more popular.
---
### Answer by username_11 on 2023-12-23. Score: 7
**TLDR:** Doing complementation and intersection on automata is hard. There may or may not be other ways to support these features in an indirect way

---

There are two broad categories of algorithms for matching regular expressions: **backtracking** engines and **automata-based** engines.

> in reality regular expression engine compile regexes into finite automata.

This is arguably incorrect. A large number of the regular expression libraries included with popular programming languages including Python, Java, Javascript and libraries like PCRE are based on backtracking. There are relatively few regular expression engines which are based on automata. Notable examples include RE2 and Hyperscan.

Backtracking is exponentially slow in the worst case. However, in practice, regular expressions are frequently used for simple text-processing tasks in which case the performance of these engines are not so bad. I suspect the main reason that backtracking is used so widely in practice is because it is easy to implement, and the implementations are very flexible, allowing the addition of non-classical features like lookarounds (shameless plug for [my POPL paper](https://kmamouras.github.io/papers/regex-lookaround-draft-POPL%2724.pdf)), capture groups, backreferences, etc.

How badly will backtracking be affected if negation and intersection were added? I am not sure.

---

Generally, the automata based algorithms would be based on **Non-Deterministic** Finite Automata (NFA). This is because the corresponding deterministic automata would often be too large.

It is possible to simulate/run an NFA in $O(m^2 \cdot n)$ time (where $m$ is the size of the NFA and $n$ is the size of the string. If implemented carefully, it is possible to construct an NFA from a regex of size $r$ and simulate the regex in $O(r \cdot n)$ time.

> **Intersection** in finite automata is trivial and do not blow up the size too much

Let's examine that claim. The textbook algorithm for constructing the intersection automaton for an automaton of size $a$ and another of size $b$ would produce an automaton of size $a \times b$. Thus, if you have $k$ regular expressions whose intersection you want to consider $r\_1 \cap r\_2 \cdots r\_k$, then you will create an automaton of size $r\_1 \times \cdots \times r\_k$. This 'trivial' algorithm thus results in an exponentially large Automaton.

[Rosu and Vishwanathan](https://vmahesh.cs.illinois.edu/papers/rta03.pdf) in their paper "Testing Extended Regular Language Membership Incrementally by Rewriting" have a proof of the following claim (See Theorem 1): Suppose algorithm $A$ scans a string from left to right whilst producing judgements at each step about whether the string so far matches a given regex potentially with intersection. Then, $A$ must store at least $O(2^{c\sqrt{r}})$ bits.

---

**Complementation** is harder. Complementing Deterministic Automata is easy. Complementing NFAs is not.

To complement an NFA, you *cannot* simply swap the accepting and non-accepting states. This is because, in order to demonstrate that $w \not \in L$, you need to show that *all* paths do not accept the string. The most trivial algorithm for complementation will involve determinization of the automaton first.

This means that if you have a regular expression with multiple negations inside it, you must incur an exponential cost to determinize each of them! So, with negation, the NFAs that you get are worse than any tower of exponentials. Indeed, it is known that for regular expressions with complementation, the NFAs may have [**non-elementary**](https://en.wikipedia.org/wiki/Nonelementary_problem) size.

---

Many of these lowerbound results only applies to streaming algorithms. So, it is possible that there are certain algorithms which make multiple passes on the string to match the regex which works much better. Indeed, [this](https://link.springer.com/chapter/10.1007/978-3-540-71389-0_24) paper from Rosu titled "An Effective Algorithm for the Membership Problem for Extended Regular Expressions" seems to be able to tackle this problem in polynomial time (even with complementation!). However, as far as I know this algorithm has never been implemented.

There seems to be [some](https://www.microsoft.com/en-us/research/uploads/prod/2020/08/pldi21-SBFA-final.pdf) [recent](https://www.microsoft.com/en-us/research/uploads/prod/2019/02/SRM_tacas19.pdf) research involving derivatives which seem to suggest that you can build practical regular expression engines with intersection. I am not certain how solid their theoretical guarantees are.

It appears to be the case that the regular expression fragment of logics used for assertions by hardware designers like [PSL](https://en.wikipedia.org/wiki/Property_Specification_Language) or [SVA](https://en.wikipedia.org/wiki/SystemVerilog#Assertions) do support intersection. It is unclear to me however, how well these features are supported in implementaions.
> **Comments:**
> **username_0** (2023-12-23): Nice! I thought RE got compiled to DFA via Thompson algorithm, which is my key misunderstanding.  
---
