Each Chomsky tier is matched to a recogniser — what memory does each machine add over the tier below?

## One rung, one kind of memory The hierarchy is usually first met as four restrictions on grammars. Its real force is that each restriction is matched, exactly, by a class of machine: the languages a tier's grammars generate are precisely the languages that tier's machine accepts. So the ladder can be read from either end — as "what shape may my rules have" or as "what must my validator be able to remember". The second reading is the one that survives into engineering work, because it tells you what a checker has to hold in memory while it runs. What changes from rung to rung is not how fast the machine is or how many states it has. It is the **shape of the memory** it is allowed to keep. ## The four recognisers | Tier | Recogniser | Working memory | What that memory can check | |---|---|---|---| | 3 | finite automaton | the current state, drawn from a fixed finite set | facts expressible as a bounded amount of "what I have seen so far" | | 2 | pushdown automaton | one store of unbounded depth, newest symbol readable | properly nested structure, one open context at a time | | 1 | linear-bounded automaton | a read/write region within a constant factor of the input length | relations between distant parts of a single input | | 0 | Turing machine | unbounded read/write tape | anything a mechanical procedure can confirm at all | - The **finite automaton** has no memory outside its state. Determinism is not the issue here: the nondeterministic and deterministic versions accept exactly the same languages, so nondeterminism buys convenience and state count, not power. - The **pushdown automaton** gains a store with unbounded capacity but a severe access rule — you see only what was written most recently. That is precisely the shape that matches nesting, because the innermost unclosed context is always the most recent one. - The **linear-bounded automaton** is defined as a nondeterministic tape machine that may use only the region its input occupies, up to a constant factor. It can overwrite, re-read, and walk back and forth across that region, which is what lets it compare two widely separated parts of the same input. It cannot grow scratch space beyond the input's size. - The **Turing machine** is the linear-bounded machine with the size cap removed. Because there is no bound, a run need not terminate: a type 0 machine is guaranteed to accept every member of its language, and is guaranteed nothing about a non-member. What follows from that belongs to the study of decidability, which is a neighbouring subject. ## What each memory cannot do 1. **Finite state cannot count without a bound.** It can distinguish only finitely many histories, so past some threshold two different prefixes become indistinguishable to it. If the language needed them treated differently, the machine is now wrong on some input. 2. **A last-in-first-out store cannot compare in the original order.** Reading it back gives the reverse of the order it was written, which is what makes mirrored structure easy and same-order repetition hard. 3. **Linear space cannot run an unbounded side computation.** Anything needing working space that grows faster than the input is out of reach. ## Why scaling a machine never promotes it A very common wrong answer is that a finite machine with enough states, or a pushdown machine with a deep enough store, reaches the next tier. It does not. "Finite" is the entire restriction at type 3: adding states moves the threshold at which two prefixes collide, but the threshold still exists, so the class of languages accepted is unchanged. In the same way, a pushdown store is already unbounded — the limitation is the access rule, not the capacity. Change the *shape* of the memory and the power really does change: give a machine two independent stores it can use freely, or a first-in-first-out store instead of a last-in-first-out one, and it reaches full tape power. Size is a constant; shape is a class. ## An honest gap at the type 1 rung The machine matched to type 1 is the **nondeterministic** linear-bounded automaton. Whether the deterministic version accepts the same class is a long-standing open question — it has not been settled either way. This is worth knowing for two reasons: it is the one rung of the ladder where the standard pairing carries a caveat, and quoting it accurately signals that you learned the hierarchy rather than a slogan about it. Contrast it with the finite-state rung, where the determinism question was settled long ago and the answer is that it makes no difference to the class. ## Reading the ladder at work When a validator is being designed, this table answers a practical question: what must the checker hold while it runs, and what does that cost on input you do not control? A constant-memory checker can be run at a trust boundary with no resource question at all. A checker with an unbounded nested-context store needs a depth limit, because the input controls how much it allocates. A checker that must re-read the whole input to relate two of its parts has to buffer the whole input, which rules out validating a stream as it arrives. The tier is not an academic label — it is the memory bill.