This is a tentative forecast of lecture contents and homework and exam dates. The forecast is subject to revision as needed. I may need to miss one or two classes for conferences and such; in these cases, I will try to get guest lecturers.
Section numbers for the readings are given for the 3rd Edition of Martin. Please don't ask me about earlier editions -- I don't know the correspondence.
| Date | Lecture Topic | Reading | Due | Assigned |
|---|---|---|---|---|
| Tues Jan 15 |
Intro; Strings and Languages | Sec 1.5 | ||
| Thurs Jan 17 |
Deterministic Finite Automata | Sec 3.3 | ||
| Tues Jan 22 |
Nondeterministic Finite Automata | Sec 4.1 | ||
| Thurs Jan 24 |
NFA-DFA Equivalence | Sec 4.1 | Homework 1 | |
| Tues Jan 29 |
lambda-NFAs | Sec 4.2 | ||
| Thurs Jan 31 |
Regular Expressions; Kleene's Theorem | Secs 3.1,4.3 | ||
| Tues Feb 5 |
Finish Kleene's Theorem | Sec 4.3 | ||
| Thur Feb 7 |
Proving languages non-regular; the Pumping Lemma for RLs | Sec 5.3 | Homework 1 | Homework 2 |
| Tues Feb 12 |
Closure and Decision Problems for RLs | Sec 5.4 | ||
| Thurs Feb 14 |
Quotients of a Language; Myhill-Nerode Thm | Secs 3.2,5.1 | ||
| Tues Feb 19 |
DFA Minimization | Secs 3.4,5.2 | ||
| Thurs Feb 21 |
(Probably Finishing Up RLs) | |||
| Tue Feb 26 |
Context-Free Languages and Grammars | Secs 6.1,6.2 | Homework 2 | |
| Thur Feb 28 |
Exam 1 | |||
| Tues Mar 4 |
CFLs Strictly Contain the RLS; Ambiguity | Secs 6.3,6.4 | ||
| Thurs Mar 6 |
Push-Down Automata: Machines for CFLs | Secs 7.1,7.2 | ||
| Mar 10-14 | Spring Break | |||
| Tues Mar 18 |
Equivalence of CFLs and PDAs, Part 1 | Sec 7.4 | ||
| Thurs Mar 20 |
Equivalence of CFLs and PDAs, Part 2 | Sec 7.5 | Homework 3 | |
| Tues Mar 25 |
Chomsky Normal Form for CFGs | Sec 6.6 | ||
| Thurs Mar 27 |
The Pumping Lemma for CFLs | Sec 8.1 | ||
| Tues Apr 1 |
Closure Properties and Decision Procedures for CFLs | Secs 8.2,8.3 | ||
| Thurs Apr 3 |
Introduction to Turing Machines | Secs 9.1,9.3 | ||
| Tues Apr 8 |
Simulating Extensions to TMs | Secs 9.4,9.5 | Homework 3 | Homework 4 |
| Thur Apr 10 |
RE and Recursive Languages | Secs 9.7,10.1,10.2 | ||
| Tue Apr 15 |
Universal TMs and Existence of non-RE Languages | Secs 9.6,10.5 | ||
| Thur Apr 17 |
Undecidable Problems on TMs | Sec 11.1 | ||
| Tues Apr 22 |
Proving a Language Nonrecursive: Turing Reduction | Secs 11.2,11.3,11.4 | Homework 4 | |
| Thur Apr 24 |
Exam 2 |