Subject | Slides | Video | Readings | |
---|---|---|---|---|

Course Introduction | 1-1-1 | Chapter 1 | ||

Introduction to Automata | 1-2-2 | Section 2.1 | ||

Deterministic Finite Automata | 1-3-3 | Section 2.2 | ||

NFA, ε-NFA, Rabin-Scott subset construction | 1-4-4 | Sections 2.3 - 2.5 | ||

Regular Expressions | 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 | Sections 4.1, 4.3, 4.4 | |||

Closure Properties of Regular Languages | 2-4-8 | Section 4.2 | ||

Context-Free Languages | Section 5.1 | |||

Parse Trees | Sections 5.2, 5.4 | |||

Normal Forms for Context-Free Grammars | Section 7.1 | |||

Pushdown Automata | 3-4-12 | Sections 6.1, 6.2 | ||

Equivalence of CFG's and PDA's | Section 6.3 | |||

The Pumping Lemma for Context-Free Languages | Section 7.2 | |||

Properties of Context-Free Languages | Sections 7.3, 7.4 | |||

Enumerations, Turing Machines | Sections 8.1, 8.2 | |||

More About Turing Machines | Sections 8.3 - 8.6 | |||

Undecidable Problems | Sections 9.1, 9.2 | |||

More Undecidable Problems | Sections 9.3 - 9.5 | |||

NP-Completeness | Section 10.1 | |||

Satisfiability, Cook's Theorem | Sections 10.2, 10.3 | |||

More NP-Complete Problems | Sections 10.4, 11.1 | |||

PSPACE-Complete Problems | Sections 11.2, 11.3 |