Date 
Lecture 
Readings 
Homework 
9/20 
Course Introduction, Finite Automaton: definition, examples 
0.1  0.4, 1.1 

9/25 
Regular operations, nondeterminism 
1.2 

9/27 
NFA's, regular ops 
1.3 

10/2 
Reg. exp.'s 
1.3 
HW 1 
10/4 
Review session: Sample problems we will do in class 
1.11.3 

10/9 
NonRegular Languages, Pumping Lemma 
1.4 
HW 1 Answer Sheet 
10/11 
Pumping Lemma Proof, size of NFA's, DFA's 
1.4 

10/16 
Quiz 1, Mandeville Aud. Intro to CFG's 
2.1 

10/18 
Contextfree grammars, parse trees, ambiguity 
2.1 

10/23 
Chomsky Normal Form, Pushdown automata 
2.2 

10/25 
More PDA 
2.2 
HW 2 
10/30 
Pumping Lemma, NonCFL (notes last lecture) 
2.3 
HW 2 Answer Sheet 
11/1 
Intro to Turing Machines 
3.1 

11/6 
Quiz 2, Mandeville Aud. Variants of TM 
3.2 

11/8 
More Variants, Equivalence 
3.2, 3.3 

11/13 
Decidable Problems 
4.1 

11/15 
Undecidability, The Halting Problem 
4.2 
HW 3 
11/20 
Reducibility 
5.1, 5.3 
HW 3 Answer Sheet 
11/22 
Thanksgiving Holiday 


11/27 
Quiz 3, Price Center Th., Complexity 
7.1 

11/29 
Last Lecture: P and NP 
7 

M 12/3 
Final Exam, 3  6 pm, Price Center Th. 

