On the Hardness of Learning Regular Expressions

Idan Attias, Lev Reyzin, Nathan Srebro, Gal Vardi

TL;DR

While regular expressions (regex) are a staple of everyday software engineering, their computational learnability has long remained a theoretical mystery. This paper establishes that learning succinct regular expressions from data is computationally hard under standard cryptographic assumptions, even when given uniform data distributions or the ability to actively query the target system. Crucially, the authors show that these constraints are fundamentally distinct from known hardness results for finite automata due to massive exponential gaps in how efficiently each format describes a language.

What Problem Does This Paper Address?

In machine learning and theoretical computer science, we often want to know if a computer can automatically learn a rule or concept given examples (PAC learning) or by asking questions (Membership Queries). We have known for decades that learning Deterministic Finite Automata (DFAs) is hard. Since DFAs and Regular Expressions (REs) describe the exact same set of languages (regular languages), you might think that regular expressions are automatically hard to learn too.

However, learning complexity is measured relative to the size of the representation. As the authors highlight, translating a regular expression into a DFA (or vice versa) can cause an exponential or even super-exponential explosion in size.

Table 2: Succinctness/translation blow-ups among DFA, NFA, RE, RE(∩), and RE(¬).

Because a language might have a very short, simple regular expression but a massive, complex DFA, existing DFA hardness proofs don't apply. This paper addresses this long-standing gap: Is it computationally tractable to learn a regular expression in time polynomial to the length of the expression itself?

Methods

To prove that learning regular expressions is hard, the authors use prediction-preserving reductions. They take known computationally hard problems from learning theory and cryptanalysis and show that if you could efficiently learn a regular expression, you could also solve these notoriously hard problems.

Specifically, they deploy three distinct reduction strategies:

  1. For Distribution-Free PAC Learning: They map polynomial-size Disjunctive Normal Forms (DNFs)—a classic representation of boolean logic—directly into plain regular expressions, carrying over known DNF hardness results.
  2. For Uniform Distribution PAC Learning: DNF hardness doesn't hold under uniform distributions, so the authors use a framework based on Local Pseudorandom Generators (local PRGs). They construct a clever hyperedge encoding scheme to show that an efficient regex learner could be used to distinguish truly random strings from pseudorandom ones, breaking the PRG.
  3. For Extended Regular Expressions: When regular expressions are extended with advanced operators like intersection ($\cap$) or complement ($\neg$), the authors reduce the problem from learning polynomial-size Boolean formulas, leveraging cryptographic hardness assumptions established by Kharitonov.

Datasets

Not discussed in the paper. As a purely theoretical computer science paper, the work relies on mathematical proofs and complexity-theoretic reductions rather than empirical datasets or benchmarks.

Key Insights and Ideas

  • Representation is Everything: The core takeaway is that learnability depends entirely on the description length (the "prior") induced by the model, not just the underlying concept class. Even though DFAs, NFAs, and REs are mathematically equivalent, their learning landscapes look entirely different.
  • The DFA vs. RE Asymmetry: A striking example of this asymmetry appears when the learner is allowed to make membership queries (MQ). Under this condition, DFAs become perfectly learnable in polynomial time (via Angluin’s famous $L^*$ algorithm). Yet, as this paper proves, plain regular expressions remain stubbornly hard to learn.
  • Star-Free Hardness: The authors show that the hardness of learning regular expressions under the uniform distribution holds even if you strip away the Kleene star ($*$) operator, meaning that even "star-free" regexes consisting only of unions and concatenations are hard to learn.

Key Results

The paper maps out a comprehensive taxonomy of tractability and hardness across different variations of automata and regular expressions.

Table 1: Tractability of learning regular expressions and automata. Our new hardness results are in bold font.

The primary new findings include:

  • Plain REs (supporting union, concatenation, and Kleene star) are hard to learn in a distribution-free PAC setting under several standard assumptions (local-PRG, random $k$-SAT, sparse LPN).
  • Plain REs are hard to PAC-learn even under a uniform distribution, relying on the local-PRG assumption.
  • Extended REs (with intersection or complement) are hard to learn even with the benefit of membership queries under a uniform distribution, based on standard cryptographic assumptions like RSA or factoring Blum integers.

Limitations and Future Work

While this paper maps out most of the regex learning landscape, a few intriguing questions remain open:

  • The Uniform Distribution + MQ Blindspot: The authors note that it remains unknown whether plain REs or NFAs can be efficiently learned if you combine a uniform distribution with membership queries (indicated by the question marks in Table 1).
  • Coarse-Grained Complexity: The current analysis focuses broadly on polynomial-time tractability. The authors suggest that future work could explore a more refined, finer-grained quantitative analysis of exact sample complexity and runtime bounds.
  • Reliance on Assumptions: As is standard in computational complexity, these hardness results are conditional on unproven (but widely accepted) cryptographic assumptions (like the hardness of RSA or the existence of local PRGs).

Summary updated

Abstract

Despite the theoretical significance and wide practical use of regular expressions, the computational complexity of learning them has been largely unexplored. We study the computational hardness of improperly learning regular expressions in the PAC model and with membership queries. We show that PAC learning is hard even under the uniform distribution on the hypercube, and also prove hardness of distribution-free learning with membership queries. Furthermore, if regular expressions are extended with complement or intersection, we establish hardness of learning with membership queries even under the uniform distribution. We emphasize that these results do not follow from existing hardness results for learning DFAs or NFAs, since the descriptive complexity of regular languages can differ exponentially between DFAs, NFAs, and regular expressions.
BibTeX
@inproceedings{attias2026hardness,
  author = {Idan Attias and Lev Reyzin and Nathan Srebro and Gal Vardi},
  title = {{On the Hardness of Learning Regular Expressions}},
  booktitle = {ALT},
  year = {2026},
  url = {https://openreview.net/forum?id=hVPfu5BqYx},
}
Figure