SubjectSlidesVideoReadings
Course Introduction PDF 1-1-1 Chapter 1
Introduction to Automata PDF 1-2-2 Section 2.1
Deterministic Finite Automata PDF 1-3-3 Section 2.2
NFA, ε-NFA, Rabin-Scott subset construction PDF 1-4-4 Sections 2.3 - 2.5
Regular Expressions PDF Chapter 3: Regular Expressions and Languages.
Section 3.1 Regular Expressions, Section 3.2 Finite Automata and Regular Expressions, Section 3.3 Applications of Regular Expressions, Section 3.4 Algebraic Laws for Regular Expressions.
Decision Properties of Regular Languages PDF Sections 4.1, 4.3, 4.4
Closure Properties of Regular Languages PDF 2-4-8 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 3-4-12 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