# On the Hardness of Learning Regular Expressions

arXiv: https://arxiv.org/abs/2510.04834 · HTML: https://mlsanity.com/paper/2510.04834/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 44 references that are in the map.
- First posted on arXiv 6 Oct 2025.

## Builds on (most cited first, 5 of 5)

- [What Formal Languages Can Transformers Express? A Survey](https://mlsanity.com/paper/2311.00208/) (2023)
- [From Local Pseudorandom Generators to Hardness of Learning](https://mlsanity.com/paper/2101.08303/) (2021)
- [Complexity theoretic limitations on learning DNF's](https://mlsanity.com/paper/1404.3378/) (2014)
- [From average case complexity to improper learning complexity](https://mlsanity.com/paper/1311.2272/) (2013)
- [Computational Complexity of Learning Neural Networks: Smoothness and Degeneracy](https://mlsanity.com/paper/2302.07426/) (2023)

## Built on by (most cited first, 2 of 2)

- [Learning to Think from Multiple Thinkers](https://mlsanity.com/paper/2604.24737/) (2026)
- [Stringological sequence prediction I: efficient algorithms for predicting highly repetitive sequences](https://mlsanity.com/paper/2603.26852/) (2026)

## Abstract (arXiv)

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.