Read the assigned reading before class. If you have looked at the material before it is discussed in class, you will get much more out of the class discussion. All reading listed is from the Lewis and Papadimitriou text.
Test dates are unlikely to change. The topics and assigned reading are a guide and will most likely be adjusted during the semester.
| Date | Topic | Reading | Lab |
|---|---|---|---|
| Jan 14 | Intro, Sets, Languages | Ch 1 | |
| |
|||
| Jan 19 | Languages, Reg. Expressions | Ch 1 | |
| Jan 21 | DFA, NFA | Ch 2.1-2.2 | |
| |
|||
| Jan 26 | Reg. Grammars | Ch 2.3 | |
| Jan 28 | Reg. Grammars | ||
| |
|||
| Feb 2 | Pump. Lemma and Properties | Ch 2.4 | |
| Feb 4 | Minimization, Algorithms | Ch 2.5 | |
| |
|||
| Feb 9 | CFG, Parse Trees | Ch 3.1-3.2 | |
| Feb 11 | PDA | Ch 3.3-3.4 | |
| |
|||
| Feb 16 | Parsing, LR parsing | Ch 3.6-3.7 | |
| Feb 18 | review, catchup | ||
| |
|||
| Feb 23 | Test 1 | ||
| Feb 25 | LR Parsing | ||
| |
|||
| Mar 2 | LL Parsing | ||
| Mar 4 | Prop. of CFG, Pump. Lemma | Ch 3.5 | |
| |
|||
| Mar 9 | Turing Machine | Ch 4.1-4.2 | |
| Mar 11 | Other Models of TM | Ch 4.3-4.5 | |
| |
|||
| Mar 16 | Spring Break | ||
| Mar 18 | Spring Break | ||
| |
|||
| Mar 23 | Unrestricted Grammars | Ch 4.6 | |
| Mar 25 | Undecidability | Ch 5 | |
| |
|||
| Mar 30 | Undecidability | Ch 5 | |
| Apr 1 | Undecidability | Ch 5 | |
| |
|||
| Apr 6 | review | ||
| Apr 8 | Test 2 | ||
| |
|||
| Apr 13 | Other topics | ||
| Apr 15 | |||
| |
|||
| Apr 20 | |||
| Apr 22 | |||
| |
|||
| Apr 27 | |||
| Apr 29 | Study day | ||
| |
|||
| May 6 | Final Exam - Thursday, May 6, 9am | ||