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