Theory of Computation

Foundations

The vocabulary every later machine is defined in, and what a machine is actually being asked to do.

• Alphabets, Strings and LanguagesStart here. Four definitions, built one on top of the next, and the reason a language is just a set.
• Machines and RecognitionWhat it means for a machine to accept a string — states, transitions, and the one bit of memory a finite machine is allowed.

• Proof techniques: induction and contradiction

Regular languages

The simplest machines there are — finite memory, one pass, no going back.

• Running a DFAFeed a string to a three-state machine and watch it decide, one symbol at a time.
• Running an NFAThe same language, one arrow too many — watch the machine track every possibility at once.
• Regular Expressions to NFAThompson's construction: every operator has one wiring pattern, and the whole machine is those patterns nested.
• NFA → DFA by Subset ConstructionNondeterminism buys no extra power. Watch the choices get absorbed into sets of states.
• DFA MinimisationSplit states until no block can be split again, then merge what is left. The result is provably the smallest.
• The Pumping LemmaWhy aⁿbⁿ is not regular — pigeonhole finds a loop, and the loop can be pumped into a string outside the language.

Context-free languages

Add a stack, and suddenly you can count matching brackets.

• The Chomsky HierarchyFour nested classes of language, and exactly what memory each one costs you.
• Grammars, Derivations and AmbiguityBuild the same parse tree top-down, and see why one string having many derivations is harmless but two trees is not.
• Pushdown AutomataOne stack is exactly enough to match aⁿbⁿ — and exactly not enough for aⁿbⁿcⁿ.

• CNF and CYK parsing

Turing machines

Add an unbounded tape, and you have every computer ever built.

• Turing Machine ExecutionWatch a machine cross off matching pairs on its tape — writing is what makes it stronger than a stack.

• Variants and equivalence
• The Church-Turing thesis

Decidability

The questions no machine can answer, and how we prove it.

• The Halting ProblemBuild a program whose only purpose is to disagree with the oracle about itself, and the oracle cannot exist.

• Decidable vs recognisable
• Reductions
• P, NP and NP-completeness