In a route-matching pattern, what does the Kleene star applied to a subexpression mean?
answer
- repetition, and the count starts low
- how few copies are allowed?
- zero copies is a legal split
- binds to one unit, not the sequence
- empty input satisfies a starred part
basics
~20 sThe Kleene star means zero or more repetitions of the subexpression it follows, joined end to end. Zero is the trap: a starred part can match the empty string, so on its own it never forces that text to be present.
solid answer
~30 s`R*` matches any text that splits into zero or more consecutive pieces, each matched by `R`. The star is postfix and binds to the single unit immediately before it, which is one symbol, one character class, or one parenthesised group — so `ab*` is `a` followed by any number of `b`, while `(ab)*` repeats the whole two-symbol group. The zero case is the one that bites in configuration: a route rule written `/api/v[0-9]*/users` also matches `/api/v/users`, because the starred digits may appear zero times. If you meant at least one, that is `R+`, which is shorthand for `RR*`.
go deeper
Recall the three beats: zero or more copies, joined end to end, repeating only the unit directly before the star. Be ready to say what the shortest matching text is for a small pattern.
Explain why ab* and (ab)* differ, and why a rule with a starred digit run still accepts a missing digit. Know that the one-or-more form is shorthand for a copy followed by a star.
Show where the zero-copy case has bitten a real rule — a route or validation pattern that accepts input the author never intended — and how you would tighten it without changing anything else.
Frame it as a design rule for whoever writes patterns in your configuration: a starred part expresses permission, not requirement, so review of matching rules should ask what each pattern rejects, not only what it accepts.
## What the star says The **Kleene star** is the repetition operator of the pattern formalism, named after Stephen Kleene, who introduced it when defining regular events. Written after a subexpression `R`, the pattern `R*` matches exactly the texts that can be cut into **zero or more** consecutive pieces where every piece is matched by `R` on its own. The word **zero** is part of the definition, not an edge case added later. Three consequences follow, and all three are asked about: - `R*` matches the empty string, whatever `R` is — the empty split into no pieces is always available. - `R*` places no upper bound on the number of pieces; the same finite pattern stands for an infinite set of texts. - The pieces are joined by **concatenation** and nothing else: there is no separator, no ordering rule and no requirement that the pieces be identical to each other. `(ab|c)*` happily matches `abcab`. ## What the star binds to The star is **postfix** and applies to exactly one unit — the thing written immediately to its left. That unit is a single symbol, a single character class, or a parenthesised group. It never reaches backwards across a sequence on its own: | Pattern | Repeats | Matches | Does not match | |---|---|---|---| | `ab*` | only `b` | `a`, `ab`, `abbb` | `abab` | | `(ab)*` | the group `ab` | empty, `ab`, `abab` | `abb` | | `(a\|b)*` | either symbol | empty, `a`, `abba` | `abc` | This is why parentheses exist at all: they turn a sequence into a single unit so a following star can repeat it. A candidate who reads `ab*` as *`ab` repeated* has the binding wrong, and the difference shows up the first time a rule is supposed to match a repeating path segment. ## The zero-copy trap in a real rule Imagine an edge proxy whose route rule is `/api/v[0-9]*/users`. The intent is *a version number*. What the rule actually accepts includes: 1. `/api/v1/users` — one digit, the intended case. 2. `/api/v27/users` — two digits, also intended. 3. `/api/v/users` — **zero** digits, almost certainly not intended. The third line is the whole lesson. A starred part contributes nothing to what the text must contain; it only describes what may be there. If the version is mandatory, the rule needs `[0-9]+`, which is shorthand for one copy followed by a star: `[0-9][0-9]*`. The same trap in a nastier form: a pattern every one of whose parts is starred matches the empty text. Used as a validator, such a pattern accepts empty input while looking strict, because each starred part quietly takes the zero-copy option. ## The family of repetition forms Every other repetition notation is shorthand built on the star and on concatenation: | Form | Minimum copies | Maximum copies | Equivalent | |---|---|---|---| | `R*` | 0 | unbounded | primitive | | `R+` | 1 | unbounded | `RR*` | | `R?` | 0 | 1 | `R` or empty | | `R{2,4}` | 2 | 4 | `RR(R(R)?)?` | Only the first row is an operator of the formalism. The rest are conveniences that expand into it, which is why a claim about the star is a claim about all of them. ## What the star is not Two confusions are worth naming explicitly, because they come from other notations: - It is **not a wildcard**. In shell-style file globbing a bare `*` stands for *any run of characters*; in the pattern formalism a star must follow something, and it repeats that something. The glob `*.log` and the pattern `.*\.log` mean the same thing by different means. - It does **not** say anything about which text ends up in the match when several splits are possible. Whether a starred part takes as much as it can or as little as it can is a separate question about matching order, not about what the operator means. The set of texts `R*` describes is fixed; choosing among them is a different subject. ## What an interviewer is listening for A complete answer has three beats: zero or more copies; the copies are concatenated; the star binds to the one unit before it. A candidate who adds the empty-string consequence unprompted — and can say what `/api/v[0-9]*/users` really accepts — has understood the operator rather than memorised a phrase.
- What is the shortest text that `(ab)*c` matches, and why?Just `c`. The starred group takes the zero-copy option, so nothing from `ab` is required; the only mandatory part of the pattern is the final symbol. That is the general rule: strip every starred part and what remains is the minimum the pattern demands.
- If every part of a pattern is starred, what does the pattern accept?The empty text, among everything else. Each starred part may contribute zero copies, so the pattern has no mandatory content at all. A validator built that way looks restrictive but rejects nothing that is empty, which is a common reason a supposedly strict rule lets blank input through.
- How do you write at least one copy using only the three operators?Concatenate one copy with a star over the same subexpression: `RR*`. The shorthand `R+` means exactly that. It is worth knowing the expansion, because it shows the one-or-more form is a convenience rather than a fourth operator.
Think of a form field marked optional and repeatable: leaving it blank is a valid submission, and so is filling it in forty times. The star is that field, and forgetting the blank case is how a rule ends up accepting a missing version number.
saying these in an interview costs you the question
- Says the star means one or more repetitions.
- Thinks the star applies to the whole pattern written before it.
- Reads the star as a wildcard standing for any characters.
- Assumes a starred group must appear at least once to match.
- Claims the repeated pieces must all be identical text.