The Chomsky Hierarchy as a Ladder of Memory

The hierarchy is usually presented as four grammar classes and then, separately, as four machine classes, with a line asserting they coincide. The coincidence is the interesting part. Each restriction on the shape of a production is an assertion about what the machine must remember, and the four levels differ in exactly one dimension: the kind of auxiliary storage the recogniser is allowed.

Four stores, four classes

Level	Grammar restriction	Recogniser	Store	Membership cost
Type 3	A → aB or A → a (one side linear)	Finite automaton	none	O(n) time, O(1) space
Type 2	A → α, with A a single nonterminal	Pushdown automaton	one stack	O(n³) general, O(n) for deterministic subclasses
Type 1	αAβ → αγβ with γ ≠ ε	Linear-bounded automaton	tape bounded by c·n	decidable, no useful practical bound
Type 0	α → β, α ≠ ε	Turing machine	unbounded tape	semi-decidable

The type 1 row deserves a note on the restriction γ ≠ ε. A context-sensitive rule may not shorten the sentential form, so every derivation is non-decreasing in length. That monotonicity is what makes membership decidable: from a start symbol of length 1 and a target of length n, every intermediate form has length at most n, and there are finitely many strings over a finite alphabet of length at most n. Exhaustive search terminates.

The corresponding machine is the linear-bounded automaton, a Turing machine whose tape is confined to the cells occupied by the input plus a constant number of markers at each end. The tape length is c·n for a fixed c, not n exactly; the constant absorbs the end markers and any fixed working area. Because the tape is bounded, the number of configurations is finite, so the machine either halts or repeats a configuration, and repetition is detectable.

Why the stack is exactly what context-free buys

A pushdown automaton is a finite-state machine with one stack, and its transitions may push, pop, or ignore the top symbol. The stack gives last-in-first-out access to a record of decisions, and that is precisely the discipline a derivation needs when a nonterminal is replaced by a sequence of symbols whose expansions must be completed in reverse order.

The simulation is direct. Run a derivation in leftmost order; the unexpanded suffix of the sentential form is a stack, with the leftmost symbol on top. Expanding A into X₁X₂…Xₖ pops A and pushes Xₖ, then Xₖ₋₁, …, then X₁, so that X₁ is processed next. When the stack is empty and the input is exhausted, the string is accepted. Every context-free grammar therefore compiles to a nondeterministic pushdown automaton with the nonterminal set as its stack alphabet.

The converse direction is the one that explains the class boundary. A pushdown automaton can be converted to a context-free grammar by taking triples (p, A, q) as nonterminals, meaning “from state p with A on top of the stack, reach state q having popped A”. The construction is finite because the state set and stack alphabet are finite, and it produces a grammar whose derivations mirror the machine’s runs. Nothing in it uses a second stack.

Two stacks are a different story. A machine with two stacks can simulate a Turing machine tape by keeping the portion left of the head on one stack and the portion right on the other, moving the head by popping from one and pushing to the other. Two stacks therefore give type 0 power. The level between the pushdown automaton and the Turing machine is filled not by a stack machine but by the linear-bounded automaton, whose store is a tape bounded by the input length; the hierarchy separates its levels by the kind of store, not by a count of stacks.

The nesting that separates type 2 from type 3

The canonical witness is {aⁿbⁿ : n ≥ 1}. A finite automaton has finitely many states, so on the a-phase some state repeats; the loop between the two visits can be pumped, and the resulting string has unequal counts. A pushdown automaton pushes one symbol per a and pops one per b, then accepts on an empty stack. The count is stored as stack height, and stack height is unbounded.

The next witness separates type 1 from type 2. The language {aⁿbⁿcⁿ : n ≥ 1} is context-sensitive but not context-free. A pushdown automaton can match the a’s against the b’s, but after the stack is empty it has no record of n, and the c’s cannot be checked. A linear-bounded automaton can, because it can rewrite the a’s into a marker symbol while counting the b’s, then reuse the markers to count the c’s. The tape is long enough — it is the input itself.

These two witnesses are the standard textbook separation, and they generalise: {aⁿbⁿcⁿdⁿ…} with k distinct letters needs storage proportional to the count, which a stack cannot provide for k ≥ 3. What the stack provides is a single counter, and a single counter is enough for one matching pair.

Grammar restrictions and machine restrictions are the same restriction

The correspondence is often stated as a table, but the reason it holds is a translation in both directions that preserves the language and is effective — each construction is an algorithm on finite descriptions.

• Type 3 → finite automaton: the nonterminals become states, as Right-Linear Grammars and the Limits of One-Way Derivation sets out.
• Type 2 → pushdown automaton: the leftmost-derivation simulation above, with the sentential-form suffix as the stack.
• Type 1 → linear-bounded automaton: the non-context-sensitive rules αAβ → αγβ become tape operations that inspect a neighbourhood and rewrite it, and the non-shortening property keeps the tape within the input bounds.
• Type 0 → Turing machine: a rule α → β is a rewrite of a finite string anywhere on the tape, which is what a Turing machine transition does when it moves and writes.

Each arrow is a compilation, and each compilation is where the expressiveness question is settled. If the grammar restriction prevents a construction, the machine cannot exist either, because a machine would compile back to a grammar of the restricted form. The equivalence is not an analogy; it is a pair of translations.

What the hierarchy does not capture

The four levels are a coarse classification, and several important classes fall inside a level without being characterised by it.

Deterministic context-free languages are a proper subclass of type 2, recognised by deterministic pushdown automata. They are exactly the languages with an LR(1) grammar, and they are closed under complement while the full class is not. The gap matters because practical parsers accept the deterministic subclass, and a grammar that is context-free but not deterministic cannot be parsed by an LR parser without conflict.

Linear languages, generated by grammars whose right sides contain at most one nonterminal but may place it on either side, sit strictly between types 2 and 3, as the mixed-orientation example in Right-Linear Grammars and the Limits of One-Way Derivation shows.

Context-sensitive versus decidable is a further gap. Type 1 languages are decidable, and every decidable language is type 0, but not every decidable language is context-sensitive. The hierarchy orders grammars by rule shape, not by the complexity of the recognition problem; the resource-based classification of problems is a separate axis, and the two do not line up.

The type 0 membership problem is only semi-decidable. A Turing machine that accepts w may run forever on w ∉ L, so the best available procedure is to simulate and wait. That asymmetry — accept is a finite event, reject is not — is the same one that makes the halting problem undecidable, and it is the reason type 0 is the top of the grammar hierarchy rather than a practical specification language.

Rule shape versus recognition cost do not line up. A type 2 grammar whose rules are all binary can be recognised faster than one with long right sides, and a type 1 grammar restricted to a single left context is far cheaper to handle than the general form. The hierarchy fixes the level, not the algorithm, which is why Context-Sensitive Rules and Why Non-Contracting Rewriting Is Decidable starts from the monotonicity restriction rather than from the rule syntax, and why Chomsky Normal Form and the CYK Table spends most of its length on a transformation rather than on the recogniser.

Reading the hierarchy as a specification design guide

The practical use of the table is not classification but selection. A specification that must be checked for equivalence needs type 3, because equivalence is decidable there and undecidable for type 2 grammars. A specification that must express nested structure — matched brackets, balanced tags, nested scopes — needs at least type 2, and will lose complement and equivalence. A specification that needs to enforce agreement between three or more independent counts needs type 1, and with it a recognition cost that is exponential in the worst case and not implementable at interactive speed.

The ladder also predicts where a specification language will fail. Adding a feature that lets a rule inspect its neighbours moves a type 2 grammar toward type 1. Adding a feature that lets a nonterminal appear on both sides of a rule moves a type 3 grammar out of the regular class. Each such extension should be treated as a decision about which theorems the language is willing to give up, because the hierarchy says those theorems cannot be recovered.

The classification itself is a mechanical test on rule shape, and writing it out as code makes the four levels concrete rather than nominal:

def classify(productions):
    """Classify a grammar given as a list of (lhs, rhs) symbol-tuple pairs.
    Returns 3 (regular), 2 (context-free), 1 (context-sensitive), 0 (other).
    Every symbol appearing on a left side is treated as a nonterminal, so a
    nonterminal that is never rewritten would be mistaken for a terminal."""
    nts = {s for lhs, _ in productions for s in lhs}
    if all(len(lhs) == 1 for lhs, _ in productions):
        # Type 3 requires one terminal and at most one nonterminal per right
        # side, with the nonterminal always on the same side of the terminal.
        right_linear = left_linear = True
        for _, rhs in productions:
            if len(rhs) <= 1:
                continue                            # A -> a, A -> B, A -> eps
            terms = [s for s in rhs if s not in nts]
            nonterms = [s for s in rhs if s in nts]
            if len(terms) != 1 or len(nonterms) > 1:
                right_linear = left_linear = False  # e.g. S -> SS
            elif nonterms and rhs.index(nonterms[0]) > rhs.index(terms[0]):
                left_linear = False                 # terminal first
            elif nonterms and rhs.index(nonterms[0]) < rhs.index(terms[0]):
                right_linear = False                # terminal last
        return 3 if (right_linear or left_linear) else 2
    # A left side longer than one symbol: context-sensitive only if no rule
    # shortens the sentential form, otherwise an unrestricted rewrite system.
    for lhs, rhs in productions:
        if len(rhs) < len(lhs):
            return 0
    return 1

The function returns 3 for the right-linear and left-linear grammars of Right-Linear Grammars and the Limits of One-Way Derivation, 2 for a grammar with a genuinely context-free rule such as S → SS, 1 for a rule set with a multi-symbol left side and no shortening rule, and 0 as soon as one rule can delete symbols. The rule shapes are the whole classification; no analysis of the generated language is required, and none is possible in general.