Date 
Description 
Textbook References 
May 17 
Introduction to automata theory and some background
[Slides ] 
Hopcroft, Motwani, and Ullman: Chapter 1 –or– Sipser: Chapter 1 
May 21 
Finite Automata and their properties [Slides] 
Hopcroft, Motwani, and Ullman: Section 2.1, 2.2, and 2.3 –or– Sipser: Section 1.1 
May 22 
Tutorial class—no new concepts were introduced. 
May 24 
Nondeterminism and Alternation [Slides] 
Hopcroft, Motwani, and Ullman: Section 2.3, 2.4, 2.5, and 4.2–or–Sipser: Section 1.2 
May 28 
Regular Expressions [Slides] 
Hopcroft, Motwani, and Ullman: Chapter 3–or–Sipser: Section 1.3 
May 29 
Tutorial class—no new concepts were introduced. 

May 31 
Lecture postponed to June 3rd. 

June 3 
Pumping Lemma, Minimization, and MyhillNerode Theorem [Slides] 
Hopcroft, Motwani, and Ullman: Chapter 4–or–Sipser: Section 1.4 
June 4 
Definition of Turing machines, examples, variants, the Church Turing thesis [Slides] 
Hopcroft, Motwani, and Ullman: Chapter 8–or–Sipser: Chapter 3 
June 5 
Tutorial class—no new concepts were introduced. Quiz. 

June 7 
Decidability (recursive) and Turing recognizability (r.e),
Undecidable languages (the Halting problem), and some more properties of decidable and
r.e languages [Slides] 
Hopcroft, Motwani, and Ullman: Chapter 9 –or–Sipser:Chapter 4 
June 10 
Reductions, more undecidable problems, PCP, and counter machine [Slides] . 

June 11 
Tutorial class 

June 12 
MidSemester Exam. 

June 18 
Pushdown automata (PDA), acceptance by final states and empty stack, nondeterministic and deterministic PDA,
Introduction to context free grammars (CFG)


June 19 
More on context free grammars, tutorial 
