Reminder: Final exam is on Friday, December 7, in class.Homework 7 has been handedout, it is due on Wednesday, December 5 (5:00pm). Leave it in my mail box or under my office door.




1. Tuesday August 27  Mathematical Preliminaries  1.1  class1.ppt class1.ps 
2. Friday August 31  Languages & Finite Automata  1.2 (languages) & 2.1  class2.ppt class2.ps 
3. Tuesday September 4  Nondeterministic Finite Accepters  2.2  2.3  class3.ppt class3.ps 
4. Friday September 7  Regular Expressions  3.1  3.2  class4.ppt class4.ps 
5. Friday September 14  Regular Grammars  3.3  class5.ppt class5.ps 
6. Tuesday September 18  Properties of Regular Languages
Pumping Lemma 
4.1 (simple set operations), 4.2
4.3 
class6.ppt class6.ps 
7. Friday September 21  Pumping Lemma Examples
Lex 
4.3  class7.ppt class7.ps 
8. Tuesday September 25  ContextFree Languages  5.1 & 5.2 (ambiguity)  class8.ppt class8.ps 
9. Friday September 28  Parsing
Simplifications of ContextFree Grammars 
5.25.3
6.1 
class9.ppt class9.ps 
10. Tuesday October 2  Normal Forms
Pushdown Automata 
6.2  6.3
7.1 
class10.ppt class10.ps 
11. Friday October 5  Pushdown Automata and ContextFree Lang.  7.2  class11.ppt class11.ps 
12. Friday October 12  Deterministic Pushdown Automata
Properties of ContextFree Languages 
7.3
8.2 
class12.ppt class12.ps 
13. Tuesday October 16  Properties of ContextFree languages
Pumping Lemma for ContextFree Languages 
8.2
8.1 
class13.ppt class13.ps 
14. Friday October 19  Pumping Lemma Examples
Yacc 
8.1  class14.ppt class14.ps 
Tuesday October 23  Review class  See message 115 on webCT  
15. Tuesday October 30  Turing Machines  9.1  class15.ppt class15.ps 
16. Friday November 2  Turing Thesis  9.19.3  class16.ppt class16.ps 
17. Tuesday November 6  Variations of Turing Machines  10.1  10.3  class17.ppt class17.ps 
18. Friday November 9  Universal Turing Machine  10.4  10.5  class18.ppt class18.ps 
19. Tuesday November 13  Recursive and Recusrvively Enumerable Languages  11.1  class19.ppt class19.ps 
20. Friday November 16  Chomsky's Hierarchy
Decidability 
11.211.4
12.1 
class20.ppt class20.ps 
21. Tuesday November 20  Decidability  12.112.2  class21.ppt class21.ps 
22. Tuesday November 27  The PostCorrespondence Problem  12.3  12.4  class22.ppt class22.ps 
23. Friday December 30  Other Models of Computation
Computational Complexity 
13
14 
class23.ppt class23.ps 



1. homework1.doc homework1.ps  solution1.doc solution1.ps  Tuesday September 18 
2. homework2.doc homework2.ps  solution2.pdf solution2.ps  Tuesday October 2 
3. homework3.doc homework3.ps  solution3.doc solution3.ps  Tuesday October 16 
4. homework4.doc homework4.ps  solution4.doc solution4.ps  Friday November 2 (after extension) 
5. homework5.doc homework5.ps  solution5.pdf solution5.ps  Tuesday November 13 
6. homework6.doc homework6.ps  solution6.doc solution6.ps  Wednesday November 27 (after extension) 
7. homework7.doc homework7.ps  solution7.doc solution7.ps  Wednesday December 5 
All homeworks should be returned on the due day at the beginning of the class.
Project 2  Yacc
Send me any course related link you find and I will post it here
Text EditorsPowerpoint Viewer: viewer for powerpoint documents for Microsoft Windows Acrobat Reader: viewer for pdf files GhostView: viewer for postscript (.ps) and pdf files for Microsoft Windows and Unix
Text ProcessorsEmacs: editor for Microsoft Windows
Latex: text processor for Microsoft Windows