Elaine Rich Prentice Hall, 2008 ISBN: 9780132288064 |
Week | Date | Topics | Readings | Notes | Events | |
1 | Aug 28/30 | Mathematical background | Appendix A | AppA.pdf | a1.doc due Sep 11 5pm | |
2 | Sep 4/6 | Languages and strings | Chapter 2 | ch2.pdf | Sep 4 Labor Day no class | |
3 | Sep 11/13 | The big picture: a language hierarchy | Chapters 3-4 | ch3-4.pdf | a2.doc due Sep 20 5pm | |
4 | Sep 18/20 | Finite State Machines | Chapter 5 | ch5.pdf | a3.doc due Oct 2 5pm | |
5 | Sep 25/27 | |||||
6 | Oct 2/4 | Regular expressions/grammars Regular and nonregular languages |
Chapters 6-7 Chapter 8 |
ch6-7.pdf ch8.pdf |
tutorial.pdf; mini.doc due Oct 16 5pm a4.doc due Oct 16 5pm | |
7 | Oct 9/11 | |||||
8 | Oct 16/18 | Context-free grammars | Chapter 11 | ch11.pdf | a5.doc due Oct 30 5pm | |
9 | Oct 23/25 | Pushdown automata Context-free and non-context-free languages |
Chapter 12 Chapters 13-14 |
ch12.pdf ch13-14.pdf |
||
10 | Oct 30/Nov 1 | Turing machine | Chapter 17 | ch17.pdf | a6.doc due Nov 27 5pm | |
11 | Nov 6/8 | Church-Turing thesis; Halting problem; D and SD; Reduction | Chapters 18-21 | ch18-21.pdf | ||
12 | Nov 13/15 | Complexity | Chapters 27-28 | ch27-28.pdf | ||
13 | Nov 20/22 | Nov 22 Thanksgiving no class | ||||
14 | Nov 27/29 | Review | review.pdf | |||
15 | Dec 4/6 | Final1 | last lecture | |||
16 | Dec 8 | Final2 | 5-7:30pm |