The Big Map: The Chomsky Hierarchy

From a pile of definitions to a journey

In the last four guides you collected the raw vocabulary of this whole subject: an alphabet Sigma (the Greek capital Σ, your fixed set of allowed symbols), strings built by concatenation, the giant universe Sigma-star of every finite string, and a formal language as nothing more than a chosen set of strings carved out of that universe. You also saw the great reframing: a yes/no problem can be encoded as a language, so 'solve the problem' becomes 'decide which strings are in the set.' This guide does not add a new gadget. Instead it pulls back to show you the shape of everything still ahead.

Here is the single most important idea of the whole course. Not all languages are equally hard to describe. Some can be recognized by a machine with almost no memory; some need a little bookkeeping; some need a full general-purpose computer; and some — astonishingly — cannot be recognized by any machine at all. The map that organizes languages by 'how much machinery does it take' is called the Chomsky hierarchy. Once you have this map in your head, every later guide will feel like exploring one region of a territory you already know the outline of.

Four nested rings of languages

Picture four rings drawn one inside the next, like tree rings. The innermost ring is the smallest, most tame family; each larger ring contains everything inside it plus strictly more. The innermost ring is the regular languages: patterns simple enough that a machine with a fixed, finite memory can recognize them — think of a turnstile that only ever remembers which state it is currently in. The next ring out is the context-free languages: patterns that need a single stack of plates you can only touch from the top, which is just enough memory to match nested things like balanced brackets. Further out come languages needing a full general-purpose machine, and the outermost ring holds languages no machine can fully handle.

The crucial word is nested: every regular language is also context-free, and every context-free language can be handled by the bigger machines too. But each ring is strictly larger — there are genuine languages living in a ring that simply cannot be expressed by any machine of an inner ring. The textbook witness is the equal-counting language a^n b^n (some number of a's followed by exactly that many b's). It is context-free (a stack can count the a's and cancel them against the b's), but it is NOT regular, because a fixed finite memory cannot remember an unbounded count. Proving that gap honestly is what a later tool, the pumping lemma, is for.

Each ring has a matching machine

The beauty of the hierarchy is that each ring is not just a fuzzy idea of difficulty — it is exactly captured by one kind of machine. A finite automaton is like a vending machine or a turnstile: it has a handful of states, reads the input one symbol at a time, and on each symbol jumps to a new state via a rule we write delta(q, a) = p (in state q, on reading symbol a, go to state p). It has no scratch paper — its entire memory IS which of its finitely many states it is in. That is exactly the power needed for, and no more than, the regular languages.

Add one piece of memory — a stack of plates where you may only push onto or pop off the top — and you get a pushdown automaton, which recognizes exactly the context-free languages. The stack is just enough to match a^n b^n: push a plate for each a, then pop one plate for each b, and accept only if the stack empties out exactly as the input ends. Remove all restrictions on memory — give the machine an endless notebook it can read, erase, and rewrite at any spot — and you reach the Turing machine, the model of a general-purpose computer. Its languages form the two outermost rings.

RING            LANGUAGE FAMILY          MATCHING MACHINE         MEMORY
--------------  -----------------------  -----------------------  -------------------
innermost       regular                  finite automaton (DFA)   finite states only
     |          context-free             pushdown automaton       one stack (top only)
     v          decidable                Turing machine (halts)   unbounded tape
outermost       recursively enumerable   Turing machine (may loop) unbounded tape

example that escapes each inner ring:
  a^n b^n        regular?  NO   context-free?  YES
  a^n b^n c^n    cf?       NO   decidable?     YES

The outermost ring, and a wall that cannot be climbed

The two outermost rings are subtle and worth pausing on. A language is decidable if some Turing machine always halts and gives the right yes/no answer — it never runs forever. A language is recursively enumerable (also called Turing-recognizable) if some machine accepts every string that is in the language, but on strings that are NOT in it the machine is allowed to loop forever instead of saying no. So a recognizer can leave you waiting with no answer; a decider always comes back. This means Turing-recognizable is strictly weaker than decidable: there are languages you can recognize but never decide.

And there is a hard wall even further out. The halting problem — given the code of a program and an input, will it eventually halt or loop forever? — is undecidable: no Turing machine can answer it correctly for all inputs. This is not 'too slow' or 'too hard for now'; it is a proven mathematical impossibility, established by a self-referential trick called diagonalization. The sketch is short and worth seeing once.

1. Suppose, for contradiction, a program H exists that takes any program P and input x and always correctly answers whether P halts on x.
2. Build a sneaky program D that takes a program P, runs H on the pair (P, P), and then does the opposite: if H says 'P halts on P,' then D loops forever; if H says 'P loops,' then D halts.
3. Now feed D its own code: ask whether D halts on D. If H says it halts, D was built to loop — contradiction. If H says it loops, D was built to halt — contradiction either way.
4. Since assuming H exists forces a contradiction, no such H can exist. The halting problem has no general solver — full stop.

Why it always comes back to one question

Whatever ring you are in, the activity is always the same one you met when a problem became a language: deciding membership. Is this string in this language? A finite automaton answers it by reading the string and checking whether it ends in an accept state; a pushdown automaton answers it with the help of its stack; a Turing machine answers it by computing on its tape. The whole hierarchy is really a hierarchy of how expensive it is to answer that one question, and the undecidable wall is the point where the question has no algorithmic answer at all.

Beyond the decidable line, the questions change flavour but not spirit. Once we agree to study only problems a computer CAN solve, we start asking how efficiently — and that opens the world of complexity classes like P (solvable in time that grows only polynomially with input size) and NP (answers easy to check, like a finished jigsaw puzzle, even if hard to find). Two honest cautions here: NP does NOT mean 'not polynomial,' and in fact P is contained in NP; and whether P actually equals NP is one of the great open problems — unproven, not secretly known. The map tells you which territory a problem lives in; it does not pretend the borders between the hardest territories have all been surveyed.