Skip to content
Tape‑n‑Trace
PracticeSearch 26 tools

The hierarchy of language classes

The whole course, on one picture. Each ring is a class of languages and a kind of machine, and each contains the one inside it — every regular language is context-free, every context-free language is recursive, and so on outwards. What makes it a course rather than a diagram is that every containment is proper, and the proof of each is a separate technique: the pumping lemma of §4.1 pushes a language out of the innermost ring, the pumping lemma of §7.2 pushes it out of the next, and diagonalization pushes Ld out of them all.

Open a ring for its machine, its grammar, what it is closed under, its pumping lemma and what can be decided about it. The languages plotted in each ring link to the page that proves they belong there.

Nothing is plotted here. The containment is proper — a diagonal argument over the linear bounded automata produces a recursive language that no LBA accepts — but no memorable language is standard here, and the prescribed sections do not carry the argument. The map says so rather than naming one.

Each language sits in the innermost class that contains it, so a language shown in the context-free ring is context-free and not regular. The outermost region is Fig. 9.2's “not RE”.

How to place a language you have been given

  1. Try to build a finite automaton or a regular expression. If one works, it is regular and you are finished — draw it.
  2. If it will not, try the pumping lemma for regular languages: pick the adversary’s side and see whether every split can be broken. Play it out.
  3. Try a context-free grammar or a pushdown automaton. One counter’s worth of memory is what a stack buys you, so 0ⁿ1ⁿ works and aⁿbⁿcⁿ does not. Write the grammar or run the PDA.
  4. If that fails, use the pumping lemma for context-free languages — the one that splits a string five ways (§7.2.2). Same game, CFL variant.
  5. Beyond that, the question is whether a Turing machine can decide it, merely accept it, or neither. That is Chapter 9, and the answers come from reductions rather than from constructions.