Elaine Rich Prentice Hall, 2008 ISBN: 9780132288064 
Week  Date  Topics  Readings  Notes  Events 
1  Aug 26/28  Mathematical background  Appendix A  AppA.pdf  a1.doc due Sep 9 5pm 
2  Sep 2/4  Languages and strings  Chapter 2  ch2.pdf  Sep 2 Labor Day no class 
3  Sep 9/11  The big picture: a language hierarchy  Chapters 34  ch34.pdf  a2.doc due Sep 18 5pm 
4  Sep 16/18  Finite State Machines  Chapter 5  ch5.pdf  a3.doc due Sep 30 5pm 
5  Sep 23/25  
6  Sep 30/Oct 2  Regular expressions/grammars Regular and nonregular languages 
Chapters 67 Chapter 8 
ch67.pdf ch8.pdf 
tutorial.pdf; mini.doc due Oct 14 5pm a4.doc due Oct 14 5pm 
7  Oct 7/9  Contextfree grammars  Chapter 11  ch11.pdf  a5.doc due Oct 28 5pm 
8  Oct 14/16  Pushdown automata Contextfree and noncontextfree languages 
Chapter 12 Chapters 1314 
ch12.pdf ch1314.pdf 

9  Oct 21/23  Turing machine  Chapter 17  ch17.pdf  a6.doc due Nov 25 5pm 
10  Oct 28/30  ChurchTuring thesis; Halting problem; D and SD; Reduction  Chapters 1720  ch1821.pdf  
11  Nov 4/6  Complexity  Chapters 2728  ch2728.pdf  
12  Nov 11/13  
13  Nov 18/20  
14  Nov 25/27  Review  review.pdf  Nov 27 Thanksgiving break no class  
15  Dec 2  Final1  46:20pm; online course evaluation due Dec 6  
16  Dec 6  Final2  57:30pm 