Week 1
Introduction
Reading: Sipser 0, Hammack 1 & 2
Deterministic finite automata I
Reading: Sipser 1.1
Week 2
Deterministic finite automata II
No reading.
Nondeterministic finite automata
Reading: Sipser 1.2
Exercises 1 due
Week 3
Regular languages and their closure properties I
Reading: Hammack 4
Regular languages and their closure properties II
No reading.
Week 4
Regular expressions I
Reading: Sipser 1.3
Exercises 2 due
Regular expressions II
Reading: Hammack 5
Week 5
Nonregular languages and the pumping lemma
Reading: Sipser 1.4
Problem set 1 due
Proving that a language is nonregular
Reading: Hammack 6
Week 6
Exam 1
No reading.
Context-free grammars I
Reading: Sipser 2.1
Week 7
Context-free grammars II
No reading.
Push-down automata I
Reading: Sipser 2.2
Week 8
Push-down automata II
No reading.
Equivalence of CFGs and PDAs
No reading.
Week 9
Context-free languages and their closure properties
Reading: intersection of CF and regular languages
Non–context-free languages
Reading: Sipser 2.3
Week 10
Exam 2
No reading.
Turing machines; languages and input encoding
Reading: Sipser 3.1
Week 11
Turing machine variants and the Church-Turing thesis
Reading: Sipser 3.2 and 3.3
Decidable languages
Reading: Sipser 4.1
Week 12
Decidable languages
Reading: Sipser 4.1
Diagonalization and the halting problem
Reading: Sipser 4.2
Week 13
Undecidable languages
No reading.
Reductions
Reading: Sipser 5.1
Week 14
Mapping reductions
Reading: Sipser 5.3
No class: Thanksgiving
Reading: None
Week 15
TBD
Reading: TBD
TBD
Reading: TBD
Final Exam