Theory of Computation
Notes based on Formal Methods of Computer Science by Yang Ning (Sichuan University).
The theory of computation explores the fundamental capabilities and limitations of computers. It asks: what can be computed, and how efficiently?
Chapters
- Chapter 1: Finite Automata — Alphabets, strings, languages, DFA, NFA, equivalence
- Chapter 2: Regular Expressions and Regular Languages — Regular expressions, regular languages, closure properties, pumping lemma for regular languages
- Chapter 3: Context-Free Grammars — CFG definition, parse trees, ambiguity, normal forms (Chomsky, Greibach)
- Chapter 4: Pushdown Automata — PDA definition, acceptance by final state and empty stack, equivalence with CFG
- Chapter 5: Pumping Lemma for CFL — Pumping lemma for context-free languages, proving non-context-free
- Chapter 6: Turing Machines — TM definition, variations, Church-Turing thesis, recursive and recursively enumerable languages
- Chapter 7: Undecidability — Diagonalization, halting problem, Rice's theorem, reductions
- Chapter 8: Intractable Problems — P vs NP, NP-completeness, Cook-Levin theorem, polynomial-time reductions