| Week | Date | Chapter | Topics | Homework |
|---|---|---|---|---|
| 1 | 8/20-8/24 | 1 | No Class Friday Aug. 24th
Introduction to the
course. Review sets, graphs, and trees. Basic proof techniques (induction, contradiction, construction). The basic concepts: langauges, grammars, automata. | Assignment 1: Due Friday Aug 31st, Pg 13: 8, 25; Pg 27: 2, 4, 9, 12 Answer Key |
| 2 | 8/27-8/31 | 2 |
Deterministic Finite
Automata, Langagues and DFAs, Regular Langauges
Nondeterministic Finite Automata Equivilences | Assignment #2: Page 47: 1, 2, 15, 17; Page 54: 4, 8, 12; Answer Key |
| 3 | 9/3-9/7 | 3 |
No class on Monday the 3th Regular langauges and regular grammers Regular expressions Equivilences | Assignment #3: Page 62: 3, 7, 11; Page 75: 1, 4, 16a, 16b Answer Key |
| 4 | 9/10-9/14 | 3 |
Regular langauges
and regular grammers Regular expressions Equivilences | Assignment #4: Page 87: 4a, 4b, 4c, 8a, 8b, 10a; Page 96: 1, 2, 3. Answer Key |
| 5 | 9/17-9/21 | 4 |
First Midterm Exam Sept. 21
Closure properties Non-regular languages, pumping lemma. Palindromes. | Assignment #5: Page 108: 7, 12, 13 Answer Key |
| 6 | 9/24-9/28 | 4 |
Closure properties Non-regular languages, pumping lemma. Palindromes. | Assignment #6: Page 122: 4a, 4b, 4c, 5a, 14, 15a, 15b, 24, 26. |
| 7 | 10/1-10/5 | 5 |
No class Monday and WednesdayContext-free languages Context-free grammars Derivations and derivations trees Parsing and ambiguity | Assignment #6/7: Page 122: 4a, 4b, 4c, 5a, 14, 15a, 15b, 24, 26. Page 133: 2, 3, 7a Answer Key |
| 8 | 10/8-10/12 | 6 |
Normal forms Grammar simplification Chomsky and Greibech normal forms | |
| 9 | 10/15-10/19 | 7 |
Pushdown automata Nondetermistic and deterministic pushdown automata Pushdown automata and context-free languages. | Assignment #8: Page 183: 3a, 4a, 4f, 4g, 5; Page 195: 1, 5, 7; Page 200: 2, 9, 10 Answer Key |
| 10 | 10/22-10/26 | 8 | Properties of context-free languages: pumping lemma, closure properties, decision algorithms. | Assignment #9: Page 212: 1, 7c, 8b, 8c, 10; Page 220: 7, 12, 17 Answer Key |
| 11 | 10/29-11/2 | 8 and 9 |
Properties of CFL and Turing Machines | Assignment #10: Page 220: 18; Page 238: 2, 3, 7a. Answer Key |
| 12 | 11/5-11/9 | 9 |
2nd Mid-term, Friday, Nov. 9th Turing Machines Defintion, combinations Turing's thesis | |
| 13 | 11/12-11/16 | 9 |
Turing Machines Defintion, combinations Turing's thesis | Assignment #11: Page 244: 3b, 3c, 5a, 8; Page 258, 7. Answer Key |
| 14 | 11/19-11/23 | Fall Break | ||
| 15 | 11/26-11/30 | 10 | Variations of Turing Machines, stay-option, semi-inifinte tape, off-line TM, multi-tape, non-deterministic, universal. | Assignment #12: (Review for final, doesn't need to be turned in)Page 272: 3, 8; Page 284: 3, 6; Page 298: 1; Page 307: 5, 7. Answer Key |
| 16 | 12/3-12/7 | 11-12 | Recursive and recusively enumerable languages. Unsolvable problems. | |
| 17 | 12/10-12/17 | Final exam week. Final: Wednesday Dec. 12th, 10:00-12:00. |