Week 1
Introduction to regular expressions and finite automata.
- Reading: Lectures 1 through 4 from Kozen
- By Wednesday, March 31
- Problem set #1
- Due on paper by 8:30AM Wednesday, April 7.
Week 2
Nondeterministic finite automata. Connection between regular expressions and finite automata.
- Reading: Lectures 5 through 9 from Kozen
- Soon, but in any case by Friday, April 9
- Problem set #2
- Due on paper by 8:30AM Wednesday, April 14.
Week 3
Regex = DFA = NFA = NFA-ε. Pumping lemma.
- Reading: Lectures 10 through 12 from Kozen
- By Monday, April 19
Week 4
How does Python do regex? FA variants.
- Problem set #3
- Due on paper by 8:30AM Friday, April 23.
Week 5
Exam. Context-free grammars.
- In-class exam
- Monday, April 26
- Reading: Lectures 19-23
- Read 19 by April 30, 20-21 by May 7, and 22-23 by May 10.
Week 6
Midterm break. CFGs, continued.
- Problem set #4
- Partly due by 8:30AM Monday, May 10. The rest by noon Thursday, May 13. (Hand
in to my mailbox on second floor CMC if I'm not around.)
Week 7
Pumping lemma, push-down automata.
- Reading: Lectures 24-25
- Read by May 14.
- For your reading pleasure, a sample
Pumping Lemma argument
- Nothing to hand in.
Week 8
Turing machines. Undecidability.
- Reading: Lectures 28-29
- Read by May 17.
- Programming PDAs and TMs
- Due on paper by 8:30AM Wednesday, May 19.
Week 9
More on Turing machines and undecidability. Parsing.
- Takehome exam
- Due on paper by 8:30AM Monday, 24 May 2010.
- Reading: Lectures 30-33
- Read by May 26.
Week 10
Bison. Wrap-up.
- A short lab on the bison parser generator
- Monday, May 31.
- One last takehome exam
- Due on paper by 5:00PM Monday, 7 June 2010.