What is regular about a regular expression, and what does that word tell you your regex cannot do?
Regular expressions in the formal sense describe exactly the regular languages, the ones a finite automaton recognises with fixed memory, so they cannot match balanced parentheses or anything needing an unbounded count. Backreferences take practical regex past that class and cost the linear-time matching guarantee.
4 min readUpdated 2026-10-09
0
Answer
Short answer
"Regular" is a technical term. Formal regular expressions describe exactly the regular languages, which are the languages a finite automaton can recognise using a fixed number of states and no other memory. So a true one cannot match balanced parentheses, check that two counts are equal, or parse anything with unbounded nesting. The regex in your language may have features that go beyond that, and supporting them is why most engines backtrack, which is what makes some patterns exponentially slow.
Was this answer helpful?
Likely follow-ups
→Why can a regex match parentheses nested at most three deep but not arbitrarily deep?
→Your validation pattern has a nested quantifier and takes user input. How do you prove it is safe or replace it?
→A lexer is built from regular expressions but the parser is not. What is each one responsible for?
→What do you lose when you move a pattern from a backtracking engine to RE2, and how do you find out before deploying?
Regular means finite memory, which means finite automata
The term comes from Stephen Kleene, who showed in the 1950s that the languages you can describe with three operations, concatenation, alternation and repetition (the star), are exactly the languages recognised by a finite automaton. A finite automaton reads its input one character at a time and keeps nothing except which of its states it is in. It has no counter, no stack and no way to look back.
That fact answers the second half of the question. Whatever the pattern needs to remember about the input so far must fit into a number of states fixed before the input arrives. If the amount to remember grows with the input, no finite automaton can do it. Finite automata and formal regular expressions are two notations for one class of languages, so neither can.
The things a regular expression cannot do
The canonical example is balanced parentheses. To know whether (()(())) is balanced you must track the current nesting depth, and depth can be any number. An automaton with a hundred states can track depth up to some bound, but give it a string nested one level deeper and it has run out of states to tell the difference.
Loading diagram…
Look at the edge from depth 2 into reject: every additional level of nesting needs another state, and a finite machine has to stop somewhere. That is why "nested at most two deep" is regular and "nested to any depth" is not.
The same argument rules out tasks people try anyway: a^n b^n (some letters, then the same number of another), pairing every HTML opening tag with its close, or validating JSON structure. All of them need a stack, which puts them in the context-free languages a parser handles. It is also why compilers split the work. Tokens such as identifiers, numbers and operators are regular, so a lexer can be generated from regular expressions; the grammar that nests expressions inside statements is context-free, so it needs a parser.
Where practical regex stops being regular
The regex engines in Perl, PCRE, Java, JavaScript, Python and .NET are not limited to regular languages. The feature that breaks the boundary is the backreference, which requires the input to repeat whatever an earlier group captured.
import re
# Backreference: matches a^n b a^n. No finite automaton recognises this language.
re.fullmatch(r'(a*)b\1', 'aaabaaa') # matches
re.fullmatch(r'(a*)b\1', 'aaabaa') # None# Nested quantifier: on a failing input, the engine tries every way to split the a's.
re.fullmatch(r'(a+)+', 'a' * 30 + '!') # runs for an impractically long time
Backreferences are powerful enough that general matching with them is NP-complete. PCRE goes further with recursive patterns, and .NET with balancing groups, and both can match balanced parentheses. So the honest answer to "can a regex match nested brackets?" is "a regular expression cannot; some regex dialects can, because they are no longer regular".
Catastrophic backtracking comes from the engine, not the pattern
Candidates who treat the theory as trivia miss what it costs in production, and that is where this question separates answers. Most mainstream engines match by backtracking: they try one way to match, and on failure they rewind and try the next. Backreferences more or less require that strategy, because the engine must remember what each group captured on the current attempt.
Backtracking is exponential in the worst case. In the second example above, (a+)+ can divide thirty a characters among its groups in 2^29 ways, and when the final ! makes the match fail, a backtracking engine explores them all. Each extra a roughly doubles the work. When the input comes from users, that is a denial-of-service vector, usually called ReDoS.
Yet the pattern (a+)+ describes a regular language, the same one as a+. Ken Thompson showed in 1968 how to compile a regular expression to an automaton and simulate it, tracking every possible state at once rather than guessing and rewinding. That runs in time proportional to the pattern size times the input length, with no exponential case.
Engines built on finite automata make the trade explicit. RE2 and Go's regexp package guarantee time linear in the input, and refuse backreferences and lookaround to keep that promise. Rust's regex crate makes the same trade. .NET 7 added a non-backtracking option for the same reason. Choosing one for untrusted input is a design decision: you give up backreferences and lookaround, and the worst case disappears.
The strong answer joins both halves. "Regular" names a class of languages with finite memory, which tells you what you cannot match, and a guarantee of linear-time matching that your engine may have thrown away.
Regular means a finite automaton can do it, with fixed memory and no counting. If your task needs to count without a bound, use a parser. If your engine accepts backreferences, it has left that class and may be exponential on hostile input.