Week 1
Introduction to regular expressions and finite automata.
- Reading: Lectures 1 through 4 from Kozen
- By Wednesday, March 30
- Problem set #1
- Due on paper by 8:30AM Wednesday, April 6.
Weeks 2, 3
Nondeterministic finite automata. Connection between regular expressions and finite automata.
- Reading: Lectures 5 through 9 from Kozen
- By Friday, April 8
- Problem set #2
- Due on paper by 8:30AM Friday, April 15.
- Reading: Lectures 10 and 11
- By Monday, April 11
Week 4
Pumping Lemma wrap-up. Context-free languages.
- Problem set #3
- Due on paper by 8:30AM Friday, April 22.
- Reading: Lectures 12, 19, 20, and 21
- Read 12 right away, the rest by Friday
Week 5
More on context-free languages. Exam.
- Reading: Lectures 22-24
- Before the exam.
- In-class, closed-book exam: Wednesday, April 27.
- Based on material in Lectures 1-12 and 19-24. I'll discuss
the test's contents in more detail in class.
Week 6
Midterm break. Push-down automata.
- Problem set #4
- Due on paper by 8:30AM Monday, May 9.
- For your reading pleasure, a sample
Pumping Lemma argument
- Nothing to hand in.
- Hand in corrections on last week's in-class exam
- Due on paper by 8:30AM Monday, May 9. I'll record the mean of your two scores.
Week 7
Parsing. Turing machines.
- Reading: Lectures 26-27 on parsing
- Read by May 13.
- Reading: Lectures 28-29 on Turing machines
- Read by May 16.
- The very small Problem set #5
- Due on paper by 8:30AM Friday, May 9.
- An implementation of the CKY algorithm
- Due via the Courses hand-in folder by 11:59PM Monday, May 16.
Week 8
More on Turing machines. Undecidability.
- Reading: Lectures 31-34
- Read by May 20, sooner if you prefer to read stuff before it comes up in class.
- The takehome midterm exam.
- Due on paper (except for problem #7, which should be submitted via the Courses
hand-in folder) by 3:00PM Wednesday, May 25.
Weeks 9, 10
Decidability, Gödel's theorem, a visitor, etc.
- The final takehome exam
- Due electronically paper by 5:00PM Monday, June 6.