SubjectSlidesReadings
Course Introduction PDF Chapter 1
Introduction to Automata PDF Section 2.1
Deterministic Finite Automata PDF Section 2.2
Nondeterministic Finite Automata PDF Sections 2.3 - 2.5
Regular Expressions PDF Chapter 3
Decision Properties of Regular Languages PDF Sections 4.1, 4.3, 4.4
Closure Properties of Regular Languages PDF Section 4.2
Context-Free Languages PDF Section 5.1
Parse Trees PDF Sections 5.2, 5.4
Normal Forms for Context-Free Grammars PDF Section 7.1
Pushdown Automata PDF Sections 6.1, 6.2
Equivalence of CFG's and PDA's PDF Section 6.3
The Pumping Lemma for Context-Free Languages PDF Section 7.2
Properties of Context-Free Languages PDF Sections 7.3, 7.4
Enumerations, Turing Machines PDF Sections 8.1, 8.2
More About Turing Machines PDF Sections 8.3 - 8.6
Undecidable Problems PDF Sections 9.1, 9.2
More Undecidable Problems PDF Sections 9.3 - 9.5
NP-Completeness PDF Section 10.1
Satisfiability, Cook's Theorem PDF Sections 10.2, 10.3
More NP-Complete Problems PDF Sections 10.4, 11.1
PSPACE-Complete Problems PDF Sections 11.2, 11.3