25
$\begingroup$

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), 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?

$\endgroup$
13
  • 3
    $\begingroup$ 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. $\endgroup$
    – IMSoP
    Commented Dec 22, 2023 at 11:08
  • 2
    $\begingroup$ They are supported as negative and positive lookaheads. $\endgroup$
    – user23013
    Commented Dec 22, 2023 at 11:57
  • 3
    $\begingroup$ 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. $\endgroup$
    – IMSoP
    Commented Dec 22, 2023 at 17:39
  • 2
    $\begingroup$ At least in Rust's regex crate, there are no plans for complement or conjunction due to it not having enough use cases. However the crate exposes regex-syntax and regex-automata, and regex-automata contains methods for intersection and subtraction, so it's not too hard to implement on your own. $\endgroup$
    – tarzh
    Commented Dec 22, 2023 at 19:48
  • 2
    $\begingroup$ @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. $\endgroup$
    – Michael Homer
    Commented Dec 22, 2023 at 21:26

4 Answers 4

16
$\begingroup$

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.

$\endgroup$
3
  • 13
    $\begingroup$ 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. $\endgroup$
    – IMSoP
    Commented Dec 22, 2023 at 13:21
  • 7
    $\begingroup$ @IMSoP Occasionally questions about CS regular expressions pop up on SO, I tell them to ask on Computer Science because they're so far from what actual programmers deal with. $\endgroup$
    – Barmar
    Commented Dec 22, 2023 at 18:38
  • 10
    $\begingroup$ 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. $\endgroup$
    – Barmar
    Commented Dec 22, 2023 at 18:40
12
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – Michael Homer
    Commented Dec 23, 2023 at 18:18
  • 1
    $\begingroup$ 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. $\endgroup$
    – Pseudonym
    Commented Dec 23, 2023 at 23:44
  • 2
    $\begingroup$ 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. $\endgroup$
    – Pseudonym
    Commented Dec 23, 2023 at 23:53
  • $\begingroup$ @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. $\endgroup$
    – Pseudonym
    Commented Dec 25, 2023 at 12:52
8
$\begingroup$

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, PCRE, .NET regular expressions, 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)+ 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.

$\endgroup$
7
$\begingroup$

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), 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 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 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 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 recent 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 or SVA do support intersection. It is unclear to me however, how well these features are supported in implementaions.

$\endgroup$
1
  • 2
    $\begingroup$ Nice! I thought RE got compiled to DFA via Thompson algorithm, which is my key misunderstanding. $\endgroup$ Commented Dec 23, 2023 at 23:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .