Theory of Computation
Theory of Computation studies what machines can and cannot do. These lessons build the Chomsky hierarchy from the bottom up, with a state diagram for every automaton and small Python simulators for DFAs, NFAs, PDAs and Turing machines, so every claim about which strings are accepted is checked by running the machine.
1Basics
2Regular Languages
- Deterministic Finite AutomataThe DFA as a 5-tuple, transition tables and diagrams, how a DFA runs, design patterns (remainders, suffixes, substrings, counting) and the product construction.
- Nondeterministic Finite AutomataNFAs and ε-NFAs, how a nondeterministic machine accepts, ε-closure, the subset construction from NFA to DFA, and the exponential blow-up.
- DFA Minimization and Myhill–NerodeUnreachable and equivalent states, minimizing a DFA by partition refinement (and the table-filling method), and the Myhill–Nerode theorem that gives the number of states of the minimal DFA.
- Regular ExpressionsRegular expressions and their precedence, useful identities, converting a regular expression to an ε-NFA, converting a DFA back to a regular expression with Arden's theorem, and reading tricky expressions.
- Properties of Regular LanguagesClosure properties, the pumping lemma for regular languages and how to use it, decision problems, and a checklist for deciding whether a language is regular.
3Context-Free Languages
- Context-Free GrammarsGrammars, derivations and parse trees, ambiguity and how to remove it, simplifying grammars, Chomsky and Greibach normal forms, and the CYK membership algorithm.
- Pushdown AutomataThe PDA as a finite automaton with a stack, transitions and instantaneous descriptions, acceptance by final state and by empty stack, deterministic versus nondeterministic PDAs, and the equivalence with context-free grammars.
- Properties of Context-Free LanguagesClosure and non-closure properties of context-free languages, the pumping lemma for CFLs, decidable and undecidable questions about grammars, and a checklist for deciding whether a language is context-free.
4Turing Machines
- Turing MachinesThe Turing machine model, transitions and instantaneous descriptions, designing and simulating TMs, variants that add no power, the Church–Turing thesis, recursive and recursively enumerable languages, and the universal TM.
- Decidability and UndecidabilityWhy some languages cannot be recognised at all, the halting problem and its diagonal proof, reductions, Rice's theorem, Post's correspondence problem, and a table of decidable and undecidable problems.