Week 
Topics 
Assigned reading 
Homework 
8/238/27 
Introduction, DFAs, NFAs, closure properties 
Chapter 0, Chapter 1 (till page 54) 
Homework 0, Homework 1 
8/309/03 
NFAs, determinization: subset construction, closure properties 
Chapter 1 till page 66 
Homework 2 
9/069/10 
Regular expressions, Nonregular languages 
Chapter 1, till Section 1.3 
Homework 3 
9/139/17 
Pumping lemma and nonregular languages, MyhillNerode theorem 
Chapter 1 
Homework 4 
9/209/24 
Characterizing nonregular languages, DFA minimization, Contextfree grammars 
Section 2.1 
Homework 5 
9/2710/01 
Pushdown automata, review 
Section 2.2 
Midterm prep 
10/0410/08 
Midterm 1, PDACFG equivalence 
Section 2.2 
Homework 6 
10/1110/15 
Midterm 1 solutions, pumping lemma for CFLs, CYK algorithm 
Section 2.3 

10/1810/22 
Turing machines, nondeterminism 
Chapter 3 
Homework 7 
10/2510/29 
Decidability, Reducibility 
Chapter 4, Section 5.1 
Homework 8 
11/0111/05 
Reducibility 
Sections 5.1, 5.3, 6.3 

11/0811/12 
Reducibility, Review 

Midterm preparation 
11/1511/19 
Midterm 2, Reducibility 

Homework 9 
11/2912/03 
Firstorder logic 
Section 6.2, notes 
Homework 10 
12/0612/10 
Midterm 2 solutions, review 


12/1312/17 
Final exam 

