Skip to content
Tutorials Center
My learning

Topics

Lesson 59 of 59 ยท Practice and Review

Theory of Computation Review and Cheat Sheet

A complete review of the Theory of Computation: the Chomsky hierarchy, closure and decision properties, key theorems, complexity classes, plus runnable demos of the pigeonhole argument and decision algorithms.

You have travelled from finite automata to NP-completeness. This final lesson pulls everything together in one place: the hierarchy of machines and languages, the closure and decision properties you must remember, the key theorems and the central proof ideas. Use it as a revision sheet before an exam, and as a map when you need to recall how a topic connects to the others.

Two runnable demos make the main ideas concrete again: the pigeonhole argument behind every "not regular" proof, and the decision algorithms that make questions about DFAs and grammars decidable.

The big picture

Four levels of power

Regular DFA, NFA, regex
Context-free Grammar, PDA
Context-sensitive Linear bounded
Recursively enumerable Turing machine

Each level strictly contains the one before.

1 / 3
flowchart TD
    subgraph RE["Recursively enumerable (Turing machines)"]
        subgraph REC["Decidable"]
            subgraph CS["Context-sensitive (linear bounded automata)"]
                subgraph CF["Context-free (PDA)"]
                    subgraph REG["Regular (DFA, NFA, regex)"]
                    end
                end
            end
        end
    end

The Chomsky hierarchy as nested rings: type 3 (regular) inside type 2 (context-free) inside type 1 (context-sensitive) inside type 0 (recursively enumerable).

Models, grammars and languages

Type Language class Machine Grammar rules Example
3 Regular DFA / NFA A -> aB, A -> a (right-linear) even number of 0s
2 Context-free Nondeterministic PDA A -> ฮฑ a^n b^n, palindromes
1 Context-sensitive Linear bounded automaton ฮฑAฮฒ -> ฮฑฮณฮฒ, ` ฮณ
0 Recursively enumerable Turing machine any ฮฑ -> ฮฒ A_TM, HALT

Reminders that exam questions love:

  • NFAs and DFAs recognize the same languages; the subset construction can blow up the state count to 2^n.
  • Deterministic PDAs are strictly weaker than nondeterministic PDAs (palindromes). Deterministic context-free languages are closed under complement; general context-free languages are not.
  • Every NFA, regular expression and right-linear grammar can be converted into the others (Kleene's theorem, Arden's theorem).
  • Multi-tape, nondeterministic, and many other Turing machine variants add no power (they are equivalent up to polynomial or exponential slowdowns), which is the content of the Church-Turing thesis.

Closure properties

Operation Regular Context-free Decidable Recognizable
Union yes yes yes yes
Intersection yes no yes yes
Complement yes no yes no
Concatenation yes yes yes yes
Kleene star yes yes yes yes
Reversal yes yes yes yes
Intersection with a regular language yes yes yes yes

Decision problems

Question Regular (DFA) Context-free (CFG) Turing machine
Membership w โˆˆ L decidable decidable (CYK) undecidable (A_TM)
Emptiness L = โˆ… decidable decidable undecidable
Finiteness decidable decidable undecidable
Equivalence L1 = L2 decidable undecidable undecidable
Universality L = ฮฃ* decidable undecidable undecidable

The runnable demo below shows why the first column is easy. Emptiness is graph reachability: is any accepting state reachable from the start state? Equivalence uses the product construction: two DFAs are equivalent exactly when no reachable pair of states has one accepting and one rejecting component. A context-free question like "does this grammar generate anything?" is decidable by marking productive nonterminals.

Python Decision algorithms for DFAs and grammars

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Why a DFA cannot count: the pigeonhole principle

Every "not regular" proof boils down to one idea. A DFA with k states reading the strings a^0, a^1, ..., a^k must visit a state twice (k+1 prefixes, only k states). If a^i and a^j with i < j end in the same state, then whatever suffix makes the first accepted makes the second accepted too. For a^n b^n, the suffix b^i is accepted after a^i, so a^j b^i with j โ‰  i is wrongly accepted.

The demo makes this concrete: it builds random DFAs, finds the colliding pair, and confirms that the machine cannot be a correct recognizer for a^n b^n.

Python No DFA can recognize a^n b^n: the pigeonhole collision

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Every row prints alike: True next to two different correct answers (True versus False), so the machine is wrong on at least one of the two words. This is the argument behind the pumping lemma and the Myhill-Nerode theorem.

Key theorems at a glance

  • Kleene's theorem: regular expressions, NFAs and DFAs describe the same languages.
  • Myhill-Nerode: a language is regular iff it has finitely many equivalence classes of strings; the number of classes is the size of the minimal DFA.
  • Pumping lemma (regular): long strings in a regular language contain a pumpable segment within the first p symbols.
  • Pumping lemma (context-free): long strings in a context-free language can be written uvxyz with v and y pumped together.
  • Chomsky normal form: every context-free grammar can be converted to rules A -> BC and A -> a; CYK then decides membership in O(nยณ).
  • PDA โ‰ก CFG: pushdown automata and context-free grammars describe the same languages.
  • Church-Turing thesis: anything effectively computable is computable by a Turing machine.
  • Halting problem: undecidable, proved by diagonalization; Rice's theorem extends this to all non-trivial properties of recognized languages.
  • Time and space hierarchy: more time (or space) gives more power; P โŠŠ EXPTIME, L โŠŠ PSPACE.
  • Cook-Levin: SAT is NP-complete; reductions spread NP-completeness.
  • Savitch: PSPACE = NPSPACE; Immerman-Szelepcsenyi: NL = coNL.

Complexity classes in one line each

Class Meaning
L / NL decidable in (nondeterministic) logarithmic space
P deterministic polynomial time
NP polynomial-time verifiable; nondeterministic polynomial time
coNP complements of NP; no-instances have short certificates
PSPACE polynomial space (= NPSPACE)
EXPTIME deterministic exponential time
NP-hard at least as hard as every NP problem
NP-complete in NP and NP-hard

Known: L โІ NL โІ P โІ NP โІ PSPACE โІ EXPTIME, and P โ‰  EXPTIME. Open: P versus NP, NP versus coNP, P versus PSPACE.

Study tips

  • Re-derive the constructions: subset construction, product construction, Thompson, CNF conversion, Cook-Levin tableau. If you can build each one on a small example, you understand it.
  • Learn the standard languages: a^n b^n, a^n b^n c^n, ww, ww^R, primes in unary, {a^i b^j : i โ‰  j}. Most exam questions are variations on them.
  • Practice proofs in templates: pumping lemma games, reduction proofs with both directions, "in NP" proofs with certificate and verifier.
  • Test your designs by program on all short strings, as in the practice lessons.
  • Revisit the basics when something feels shaky: DFAs, the pumping lemma, pushdown automata and Turing machines.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which pair is correctly matched (language class, machine)?

    Context-free languages are exactly those recognized by nondeterministic pushdown automata.
  2. 2. Which problem is undecidable for context-free grammars?

    Equivalence of context-free grammars is undecidable. Emptiness and membership are decidable.
  3. 3. What is the central idea behind the pumping lemma for regular languages?

    The repeated state lets the string segment between the two visits be pumped any number of times.
  4. 4. Which inclusion chain is known to be correct?

    P is inside NP, NP is inside PSPACE, and PSPACE is inside EXPTIME. Whether any of these inclusions except the last is strict is unresolved, but P is not equal to EXPTIME.
  5. 5. A language L and its complement are both Turing-recognizable. Then L is

    Run both recognizers in parallel on the input; exactly one must halt, which gives a decider.

Summary

  • The Chomsky hierarchy orders regular, context-free, context-sensitive and recursively enumerable languages by the power of their machines.
  • Closure and decision properties differ sharply by level: complement fails for context-free languages, and almost everything becomes undecidable for Turing machines.
  • The pigeonhole principle is the engine of the regular pumping lemma and of Myhill-Nerode.
  • Complexity classes organize decidable problems by time and space; NP-completeness identifies the hardest problems in NP.
  • Build the standard constructions by hand, practice the proof templates, and test your designs by program.

Next: Theory of Computation overview