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 a few 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 | Class Topic | Reading | Due | Assigned |
|---|---|---|---|---|
| Mon Jan 12 |
Intro; Strings and Languages | Sec 1.5 | ||
| Wed Jan 14 |
Deterministic Finite Automata | Sec 3.3 | ||
| Mon Jan 19 |
Martin Luther King Day -- no class | |||
| Wed Jan 21 |
Nondeterministic Finite Automata | Sec 4.1 | ||
| Mon Jan 26 |
NFA-DFA Equivalence | Sec 4.1 | Homework 1 | |
| Wed Jan 28 |
lambda-NFAs | Sec 4.2 | ||
| Mon Feb 2 |
Regular Expressions; Kleene's Theorem | Secs 3.1,4.3 | ||
| Wed Feb 4 |
Finish Kleene's Theorem | Sec 4.3 | ||
| Mon Feb 9 |
Proving languages non-regular; the Pumping Lemma for RLs | Sec 5.3 | Homework 1 | Homework 2 |
| Wed Feb 11 |
Closure and Decision Problems for RLs | Sec 5.4 | ||
| Mon Feb 16 |
Quotients of a Language; Myhill-Nerode Thm | Secs 3.2,5.1 | ||
| Wed Feb 18 |
DFA Minimization | Secs 3.4,5.2 | ||
| Mon Feb 23 |
(Probably Finishing Up RLs) | |||
| Wed Feb 25 |
Context-Free Languages and Grammars | Secs 6.1,6.2 | Homework 2 | |
| Mon Mar 2 |
Exam 1 | |||
| Wed Mar 4 |
CFLs Strictly Contain the RLS; Ambiguity | Secs 6.3,6.4 | ||
| Mar 9-13 | Spring Break | |||
| Mon Mar 16 |
Push-Down Automata: Machines for CFLs | Secs 7.1,7.2 | ||
| Wed Mar 18 |
Equivalence of CFLs and PDAs, Part 1 | Sec 7.4 | ||
| Mon Mar 23 |
Equivalence of CFLs and PDAs, Part 2 | Sec 7.5 | Homework 3 | |
| Wed Mar 25 |
Chomsky Normal Form for CFGs | Sec 6.6 | ||
| Mon Mar 30 |
The Pumping Lemma for CFLs | Sec 8.1 | ||
| Wed April 1 |
Closure Properties and Decision Procedures for CFLs | Secs 8.2,8.3 | ||
| Mon Apr 6 |
Introduction to Turing Machines | Secs 9.1,9.3 | Homework 3 | |
| Wed Apr 8 |
Simulating Extensions to TMs | Secs 9.4,9.5 | Homework 4 | |
| Mon Apr 13 |
RE and Recursive Languages | Secs 9.7,10.1,10.2 | ||
| Wed Apr 15 |
Universal TMs and Existence of non-RE Languages | Secs 9.6,10.5 | ||
| Mon Apr 20 |
Undecidable Problems on TMs | Sec 11.1 | ||
| Wed Apr 22 |
Proving a Language Nonrecursive: Turing Reduction | Secs 11.2,11.3,11.4 | Homework 4 | |
| Mon Apr 27 |
finishing up Turing machines | |||
| FINALS PERIOD | Exam 2 |