Week 
Topics 
Assigned reading 
Homework 
8/268/30 
Introduction, DFAs, NFAs, closure properties 
Chapter 0, Chapter 1 (till page 54) 
Homework 1, Homework 2 
9/029/06 
NFAs, determinization: subset construction 
Chapter 1 till page 60 
Homework 3 
9/099/13 
NFAs, closure properties, subset construction, regular expressions 
Chapter 1, till Section 1.3 
Homework 4 
9/169/20 
Regular expressions, Pumping lemma and nonregular languages 
Chapter 1 

9/239/27 
DFA minimization, MyhillNerode theorem 

Homework 5 
9/3010/04 
Contextfree grammars, Pushdown automata 
Sections 2.1, 2.2 
Preparation for practice midterm 
10/0710/11 
Quiz 1 (practice midterm) 

Midterm preparation 
10/1410/18 
Midterm 1 

Homework 6 
10/2110/25 
Pushdown automata, pumping lemma for CFLs, CYK algorithm 
Sections 2.2, 2.3 
Homework 7 
10/2811/01 
Turing machines 
Chapter 3, Section 4.1 
Homework 8 
11/0411/08 
Decidability, Reducibility 
Chapter 4, Section 5.1 
Homework 9 
11/1111/15 
Reducibility 
Section 5.1 
Preparation for practice midterm 
11/1811/22 
Quiz 2 (Practice midterm) 

Midterm preparation 
12/0212/06 
Midterm 2, Reducibility 
Chapter 5, Section 6.3 

12/0912/13 
Firstorder logic, logical theories 
Section 6.2, notes 
Homework 10 
12/1612/17 
Review, Final exam 

