Theory of Computation

Standard theory of computation topics from the canonical curriculum.

Core Topics

• Finite Automata (DFA & NFA) — Tracing DFAs, the languages they recognize, and NFA-to-DFA subset construction.
• Regular Expressions & Languages — Regex syntax, the languages they denote, and Kleene's theorem.
• Pumping Lemma for Regular Languages — The standard tool for proving a language is not regular.
• Myhill-Nerode Theorem & DFA Minimization — Equivalence classes count states and pin down the minimal DFA.
• Context-Free Grammars — Productions, derivations, parse trees, and ambiguity.
• Pushdown Automata — A finite control plus a stack: the machines for context-free languages.
• Pumping Lemma for Context-Free Languages — Prove a language is not context-free by pumping uvxyz.
• Turing Machines — Tape, head, and transition function: computation one step at a time.
• Church-Turing Thesis — Algorithm equals Turing-computable: what the thesis claims and why.
• Decidability & the Halting Problem — Decidable vs. recognizable, and why the halting problem is undecidable.
• Reducibility & Undecidability — Mapping reductions transfer undecidability between problems.
• Rice's Theorem — Every nontrivial property of a machine's language is undecidable.
• The Classes P and NP — Polynomial-time deciding, polynomial-time verifying, and the open question between them.
• NP-Completeness & Cook-Levin — Polynomial-time reductions, NP-hardness, and why SAT is NP-complete.
• Space Complexity & Savitch's Theorem — Configuration counting, PSPACE versus NPSPACE, and Savitch's quadratic simulation.

Not sure where to start? Take the ten-question placement test.