Why is a pattern containing a backreference no longer a regular expression in the formal sense?
answer
- one feature refers to matched text
- operators compose sets, not occurrences
- a machine would need unbounded memory
- two runs forced to equal length
- the equivalence guarantee no longer applies
basics
~20 sA backreference demands that a later span reproduce text captured earlier, which the three operators cannot express. Patterns using one can describe non-regular languages, so no equivalent finite automaton exists and Kleene's theorem stops applying.
solid answer
~40 sConcatenation, alternation and the star describe a fixed set of texts; none of them can say *the same text as over there*. A backreference can, and that takes the notation out of the class. Take `(a*)b\1`: it describes texts of the form a-run, then `b`, then an a-run of the **same length**, and that language is not regular — a finite-state machine would need an unbounded number of states to remember the first run's length. So what tooling calls a regular expression is a **superset** of the formal object: the three operators plus features that leave the class. The practical loss is the guarantee, not the feature — any reasoning that depended on an equivalent machine existing no longer has a basis.
go deeper
Know the headline: not everything called a regular expression is one. A pattern that demands the same text appear again describes sets that the three operators cannot.
Explain why with one example language — equal runs on both sides of a separator — and say what a finite-state recogniser would have to remember to check it.
Draw the line accurately in review: grouping and assertions over regular sub-patterns stay inside the class, a backreference does not, and it is the guarantee rather than the feature that you are protecting.
Decide at the language boundary, not per rule: if operator-supplied patterns must carry a cost guarantee, the syntax accepted at load time is where that policy lives, and it should be one decision with one error message.
## What the three operators can and cannot say A pattern built from concatenation, alternation and the Kleene star describes a set of texts fixed the moment the pattern is written. Each operator composes **languages**, never **occurrences**: - Concatenation says *this set, then that set*. - Alternation says *this set or that set*. - The star says *any number of copies, each drawn independently from the same set*. Notice the word *independently*. `(ab|c)*` does not require the copies to agree with each other; `abcab` matches. There is no operator whose meaning refers back to what some earlier part of the pattern actually consumed on this particular text. That is the exact capability a **backreference** adds, and it is not a repetition shorthand — it is a different kind of construct entirely. ## A pattern whose language is not regular Take `(a*)b\1`, read as a whole-text match. The group captures some run of `a`, the literal `b` follows, and the backreference demands the same captured text again. The set of texts it describes is therefore > every text of the form: n copies of `a`, then `b`, then n copies of `a`, for any n. That language is **not regular**. The informal reason is a counting argument: after reading the left run, a recogniser must carry its length forward to check the right one, and the length is unbounded, while a finite automaton has a fixed number of states and no other memory. Because no finite automaton accepts this language, and Kleene's theorem is an equivalence with the regular class, the pattern is not a regular expression — whatever the file it lives in calls it. A sharper version of the same point is the copy language: `([ab]*)\1` describes texts made of some block repeated twice, which is not regular either. ## Which features leave the class and which do not This is where candidates over-correct and declare every convenience suspect. The line runs somewhere specific: | Feature | Still inside the regular class? | Why | |---|---|---| | classes, optional mark, bounded repeats | yes | shorthand that expands into the three operators | | capturing parentheses on their own | yes | grouping records *where* a match landed; the set of matching texts is unchanged | | a zero-width assertion that some regular sub-pattern does or does not match at a position | yes | the regular class is closed under intersection and complement | | a backreference to captured text | **no** | it constrains one span by another span's content, which no composition of the three operators expresses | The first three rows matter as much as the last. Saying *any feature beyond the three operators leaves the class* is wrong, and it is wrong in the direction that makes a candidate sound cautious rather than informed. ## What is actually lost The feature is not the problem; the **guarantee** is what disappears. 1. **No equivalent machine.** With the pattern inside the class, Kleene's theorem hands you a finite automaton whose size is known from the pattern. Outside the class, there is nothing to build — not *hard to build*, but *does not exist*. 2. **No structural bound on the work.** Any statement of the form *checking this rule costs at most X per input symbol* rested on that machine. Remove the machine and the statement has no support, whatever an implementation happens to do. 3. **No comparison of rules.** Deciding whether two patterns describe the same set is answerable through their machines. Without machines the question is not merely slower, it changes character. ## The design consequence If you own a configuration language whose rules are patterns — route matchers, filters, redaction rules supplied by people other than you — this is the argument for restricting the accepted syntax rather than the accepted inputs. Admit the three operators and their sugar, reject a backreference at load time with a clear message, and every rule in the file carries the machine-equivalence guarantee by construction. Admit the full notation and you have a configuration surface on which no useful claim about cost can be made at review time, because the class of object being configured is no longer the one the guarantee covers. ## What an interviewer is listening for The precise reason — a backreference constrains a span by another span's content, which composition of the three operators cannot do — and one language that demonstrates it. The strongest answer also draws the line correctly, noting that grouping and assertions over regular sub-patterns stay inside the class, so the objection is aimed at one specific feature rather than at everything unfamiliar.
- Does a zero-width assertion over a regular sub-pattern also leave the regular class?No. An assertion that some regular sub-pattern does or does not match at a position amounts to intersecting or complementing regular languages, and the class is closed under both, so the result is still regular. That is the clean distinction: assertions restrict by another regular set, while a backreference restricts by consumed text.
- Do capturing parentheses on their own take a pattern out of the class?No. Grouping records where a portion of the text was matched; it does not change which texts match. The set described by a pattern is identical with and without capture markers — only the extra information reported alongside a match differs, and that is a separate subject from the pattern's language.
- If a rule language must stay inside the class, what do you enforce and where?Enforce it on the syntax, at load time: accept the three operators and their sugar, reject anything that refers back to captured text, and fail the configuration with a message naming the offending rule. Validating at load keeps the guarantee a property of every rule in the file rather than something checked per request.
The three operators are a blueprint: they say what shapes are acceptable. A backreference is an instruction to measure the piece you just cut and make the next one identical — a different kind of order, which no blueprint of fixed shapes can contain.
saying these in an interview costs you the question
- Calls a backreference just a fourth regular operator.
- Says any repetition requirement can be written with the star.
- Believes every pattern a tool accepts has an equivalent finite automaton.
- Assumes two runs forced to equal length is still a regular language.
- Claims capturing parentheses themselves take a pattern out of the class.