Which Chomsky tier does a config format with arbitrarily nested blocks require of its validator, and why?

## The triage question When a new input format lands on a team, the first useful question is not which library to reach for — it is which tier the format's constraints live at, because that decides what class of checker can possibly be correct. Arbitrary nesting is the single most common reason a format leaves the bottom rung, and it is worth being able to say why in one breath. ## Why unbounded depth defeats finite memory Consider a validator reading a document left to right. To reject a document that closes a block it never opened, or that ends with blocks still open, it must know at every position **how many blocks are currently open**. Call that the depth. - If nesting is arbitrary, depth is **unbounded**: for any number k there is a legal document that reaches depth k. - A finite-state validator has finitely many states, and its state is the entirety of what it remembers. - So for a large enough k, two documents that reach *different* depths must land the machine in the *same* state. - From that point on the machine behaves identically on both, though the correct verdict differs — one needs k closers and the other needs a different number. - Therefore some input is judged wrongly. The machine is not merely inconvenient here; it is incorrect. This is the informal shape of the argument. The formal non-regularity proof is a separate tool with its own leaf, and you do not need it to answer the triage question: the moment you can say "the depth is unbounded and the memory is not", you have the answer an interviewer is listening for. ## What the ladder says to do instead The memory you need is the one that matches nesting: unbounded in depth, with the innermost unclosed block always the one you are working against. That is the pushdown recogniser, and its grammars are exactly type 2. In engineering terms, the format needs a **grammar and a parser**, not a pattern. | Constraint in the format | Tier needed | Shape of the validator | |---|---|---| | fixed keywords, field order, character classes | 3 | one-pass pattern, constant memory | | nesting capped at a fixed maximum depth | 3 | one-pass check, memory grows with the cap, not the input | | arbitrarily deep nesting, matched delimiters | 2 | grammar plus depth-proportional memory | | one field required to equal another distant field | 1 | structural parse plus a separate relational check | ## The bounded-depth escape hatch A depth cap genuinely changes the answer, and it is a design lever rather than a technicality. If the specification says nesting may not exceed some fixed depth and anything deeper is invalid, the set of legal documents becomes regular again: there are now only finitely many depths to distinguish, so bounded memory suffices. What you pay is machine size — the checker's state count grows with the cap — and what you must do is **reject** over-deep input explicitly rather than silently truncating or wrapping. The payoff is worth it at a trust boundary: with a cap, the memory the validator uses is fixed by your specification instead of by whoever sent the document. ## The counter that is secretly a stack A very common implementation is a pattern for the token shapes plus a depth counter in surrounding code. That is a perfectly good validator — but be honest about what it is. An unbounded counter is memory that grows with the input, so the checker as a whole sits at type 2, not type 3. Two consequences follow immediately: 1. Everything that comes with a parser is now yours to own: a depth limit, a defensible error position, and a resource bound on hostile input. 2. A single counter only works while there is one kind of delimiter. As soon as several delimiter kinds must nest correctly against each other, a count is not enough — you need to remember *which* kind was opened, in order. ## What the tier does and does not tell you The tier tells you the **class** of recogniser that is sufficient. It does not tell you which parsing algorithm to run, how to report errors, or how to recover from bad input; those are separate subjects with their own trade-offs. It also does not say the format is hard — type 2 recognition is cheap and thoroughly solved. The value of placing the format on the ladder is earlier than all that: it tells you that a checker built out of patterns alone will be wrong, and no amount of tuning the pattern will fix it. ## Saying it well in an interview The answer that lands is three sentences: the count of open blocks is unbounded, finite memory can only distinguish finitely many counts, so a pattern must eventually confuse two depths and accept something it should reject. Then add the lever — a depth cap puts you back at the bottom rung and bounds your memory — and you have shown both the theory and the judgment it pays for.