Which Chomsky tier does a format whose trailer must repeat the header verbatim land in, and why?
answer
- Same order, or reversed order?
- The abstract shape is w c w
- A last-in-first-out store hands symbols back reversed
- A non-terminal is not a bound variable
- Check the relation outside the grammar
basics
~20 sType 1, context-sensitive. An in-order copy of an unbounded string — the pattern w c w — is not context-free, because a last-in-first-out store hands symbols back reversed. A mirrored trailer would be context-free; a verbatim repeat is not.
solid answer
~50 sIt lands at **type 1**. The set of strings of the form `w c w` — some unbounded content, a separator, then the *same* content again in the same order — is the canonical witness that the context-free tier is strictly inside the context-sensitive one. The reason is the shape of the memory available at type 2: a pushdown store returns symbols in the reverse of the order they went in, so a **mirrored** trailer (`w c w` reversed) is easy and an in-order **repeat** is not. A machine that can walk back and forth over the input and compare the two halves position by position handles it, and that is the linear-bounded recogniser matched to type 1. The practical consequence is concrete: no context-free grammar can carry this constraint, so it has to be checked outside the grammar, as a named pass over the parsed result.
go deeper
Recall the headline: a grammar cannot require that two separated parts of a document be identical. Equality between distant fields is checked after parsing, not by the rules.
Explain the contrast that causes it — a mirrored trailer is context-free because the unbounded memory at that rung returns symbols reversed, while a verbatim repeat needs them back in the original order.
Show the design split you would ship: a context-free grammar for structure, a separately named relational check for the agreement, and both written into the specification rather than only into one implementation.
Own where the constraint is recorded. A relation enforced only in code becomes the format's de-facto specification, and independent implementations will disagree about it precisely because no grammar pins it down.
## The constraint that grammars cannot carry Formats routinely require one part of a document to agree with another: a trailer repeating a header, a length field matching the section it describes, an identifier used later having to match one introduced earlier. Engineers reach for a grammar, try to express the agreement, and find that no arrangement of rules does it. That is not a failure of imagination — it is the hierarchy telling them the constraint sits a rung above where they are working. The abstraction of "the trailer repeats the header" is the **copy language**: strings of the form `w c w`, where `w` is any string over the alphabet, `c` is a separator, and the second `w` is identical to the first, symbol for symbol, in the same order. This language is not context-free. It *is* context-sensitive. ## Mirror versus repeat The contrast is the whole explanation, and it is worth being able to draw it instantly. | Trailer requirement | Abstract form | Tier | Why | |---|---|---|---| | trailer mirrors the header | `w c` reverse of `w` | 2 | a last-in-first-out store returns symbols reversed, which is exactly what matching a mirror needs | | trailer repeats the header verbatim | `w c w` | 1 | matching in the original order means re-reading the stored content forwards, which that store cannot do | - At type 2 the only unbounded memory is a store whose newest symbol is the one you read. Push the header as you consume it and you get it back backwards — free mirroring, no forward copy. - At type 1 the machine may re-read a working region the size of the input. It can step to position `i` of the first half, step to position `i` of the second, compare, and repeat. Position-by-position comparison over one input is exactly the capability the rung adds. - The constraint is still perfectly **checkable**; context-sensitive is not a synonym for hard or for undecidable. It simply is not expressible in the rule shape a context-free grammar permits. ## Why a grammar cannot fake it The near-miss that almost everyone tries is to give the header a non-terminal and mention that non-terminal again in the trailer rule. It does not work, and the reason is worth internalising: a non-terminal is not a **variable bound to a string**. It is a placeholder that each occurrence rewrites independently. Writing `Doc -> Content c Content` does not say "the same content twice"; it says "some content, then some content", and the two derivations are free to differ. There is no capture, no back-reference and no equality in the formalism — that is precisely what "context-free" gives up in exchange for its cheap recogniser. The only way to force equality inside a rule system is to let rules see more than one symbol at a time and rewrite in context, which is the type 1 restriction. ## What to do about it in a real format The practical move is not to fight for a grammar that cannot exist. It is to split the specification in two: 1. **Structural layer.** A context-free grammar describes the shape: there is a header, a separator, a body, a trailer, each with its own internal syntax. A parser accepts or rejects on shape alone. 2. **Relational layer.** A separately named check, run over the parsed result, states the agreement: the trailer's content must equal the header's. It is a few lines of straightforward comparison. 3. **Specification layer.** Both are written down as rules of the format. A constraint that lives only inside one implementation's code is not part of the format; it is that implementation's private behaviour, and other implementations will diverge from it. The cost of pretending otherwise is a rule explosion. You can express a copy constraint over a *fixed, finite* alphabet and a *fixed, bounded* length by enumerating the possibilities, and the rule count grows so fast that the grammar becomes unmaintainable — and it still fails the moment the content is unbounded. ## Cross-referencing formats in general Once you can place the copy constraint, a family of everyday requirements falls into the same slot: any requirement that two separated, unbounded parts of a single document agree. Repeated identifiers, checksums computed over earlier bytes, a count that must match the number of items that follow. None of these is expressible by a context-free rule set, all of them are ordinary to check after parsing, and recognising that early saves a team from a week of trying to twist a grammar into a shape it cannot take. The interview-sized version of the answer is short: a repeat in the same order is `w c w`, which needs the rung above context-free, because the memory a grammar's recogniser gets back is reversed. The mirrored version would have been free.
- Why is a mirrored trailer easier than a repeated one?Because the unbounded memory available at the context-free rung returns its contents in the reverse of the order they were written. Consuming the header into that store and then matching the trailer against it as it comes back handles a mirror for free. An in-order copy would need to read the same store forwards, which its access rule forbids. Mirrored is type 2; repeated is type 1.
- What does landing at type 1 mean for how you build the validator?That the constraint will not live in your grammar. Parse the format with a context-free grammar to get the structure, then check the repeat as a separate, named pass over the parsed result. Trying to encode the equality in the rules produces either a grammar that quietly accepts mismatches or a combinatorial rule explosion that still fails on unbounded content.
saying these in an interview costs you the question
- Says any exact-repeat constraint is expressible context-free
- Treats a non-terminal as a variable bound to a string
- Assumes context-sensitive means the check is undecidable
- Calls the mirrored form and the repeated form the same problem
- Believes type 1 constraints cannot be validated in practice