Index of Notes
- Introduction, Finite Automata, Regular Expression
- Nondeterminism, Closure Properties, Regular Expressions → Finite Automata
- The Regular Pumping Lemma, Finite Automata → Regular Expressions, CFGs
- Pushdown Automata, Conversion of CFG to PDA and Reverse Conversion
- CF Pumping Lemma, Turing Machines
- TM Variants, the Church-Turing Thesis
- Decision Problems for Automata and Grammars
- Undecidability
- Reducibility
- The Computation History Method
- The Recursion Theorem and Logic
- Time Complexity
- Midterm Exam
- P and NP, SAT, Poly-time Reducibility
- NP-Completeness
- Cook-Levin Theorem
- Space Complexity, PSPACE, Savitch’s Theorem
Automata and Language
1-5
Computability Theory
5- 11
Complexity Theory
12 - 25