Book Sections
- Week 1:
- 8/26 Book sections 1.1-1.2 (pages 5-12), Lecture 1 (Set Theory)
- 8/28 Book sectons 1.3, (pages 13-20), Lecture 1 (Set Theory)
- Week 2:
- 8/31 Book sections 1.4-1.5 (pages 20-30), Lecture 1 (Set Theory)
- 9/2 Book section 1.7-1.8 (pages 42-51), Lecture 2 (Formal Languages)
- 9/4 Book sections 2.1 (pages 47-60) Lecture 3 (DFA)
- Week 3:
- 9/7 Holiday
- 9/9 Book Section 2.2 (pages 63-68) Lecture 4 (NFA)
- 9/11 Book Section 2.2 (pages 63-68) Lecture 4 (NFA)
- Week 4:
- 9/14 Book Section 2.3 (pages 69-77), Lecture 5 (DFA v. NFA)
- 9/16 Book Section 2.3, Lectures 6 (DFA v. Regular Expressions)
- 9/18 Book Section 2.3, 2.4 (pages 86-89) Lectures 6 and 7
- Week 5:
- 9/21 Book section 2.4 (pages 86-89), Lecture 7 (Non-Regular Languages, State Minimization)
- 9/23 Book section 2.4 (pages 86-89), Lecture 7 (Non-Regular Languages, State Minimization)
- 9/25 Book section 3.1, (pages 92-100), Lecture 8 (Context-Free Grammars)
- Week 6:
- 9/28 Book section 3.2 (pages 121-129) Lecture 8 (Context-Free Grammars)
- 9/30 Book section 3.3 (pages 130-136) Lecture 9 (PDA)
- 10/2 Book section 3.3 (pages 130-136) Lecture 9 (PDA)
- Week 7:
- 10/5 Midterm Review
- 10/7 Midterm
- 10/9 Book section 3.3 (pages 130-136) Lecture 9 (PDA)
- Week 8:
- 10/12 Book section 3.5 (pages 143-147) Lecture 10 (Non Context-Free)
- 10/14 Book section 3.5 (pages 143-147) Lecture 10 (Non Context-Free)
- 10/16 Book section 4.1 (pages 179-190) Lecture 11 (Turing Machines)
- Week 9:
- 10/19 Fall Break
- 10/21 Book Section 4.2, (pages 194-200) Lecture 11 (Turing Machines)
- 10/23 Book Section 4.2, (pages 194-200) Lecture 11 (Turing Machines)
- Week 10:
- 10/26 Book section 4.3, 4.4 (pages 200-220), Lecture 12 (Turing Machine Modifications)
- 10/28 Book section 4.3, 4.4 (pages 200-220), Lecture 12 (Turing Machine Modifications)
- 10/30 Book section 4.3, 4.4 (pages 200-220), Lecture 12 (Turing Machine Modifications)
- Week 11:
- 11/2 Book section 4.6 (pages 227-233), Lecture 13 (Unrestricted Grammars)
- 11/4 Book section 4.6 (pages 227-233), Lecture 13 (Unrestricted Grammars)
- 11/6 Counter Machines (not in book) Lecture 14 (Counter Machines)
- Week 12:
- 11/9 Book section 5.7 (pages 262-270), Lecture 16 (Enumeration Macines)
- 11/11 Book section 5.1-5.3 (pages 245-254), Lecture 15 (Undecidability) (Guest Lecture)
- 11/13 Book section 5.4-5.5 (pages 255-262), Lecture 15 (Undecidability)
Lecture Notes