CS345
AUTOMATA THEORY
FALL 2001
Lecturer: James F. Lynch
Office: SC381
Telephone: 2682374
email: jlynch@clarkson.edu
Office hours: MWF 9:30AM11:30PM
Lecture hours: MWF 1:00PM1:50PM Snell Hall 213
Text: Introduction to the Theory of Computation, by Michael
Sipser
OBJECTIVES
We will cover Chapters 05 in the text, and as much of Chapter 7 as time permits. Exercises and Problems from the text will also be assigned, and some class time will be devoted to discussion and working of some of these.
ASSESSMENT
Grading will be based on three exams and the final.
Three hourly exams: 
70% 
Final: 
30% 
Hourly exam dates: 
Wednesday, September 19 
Wednesday, October 17 

Wednesday, November 14 
SYLLABUS





Basic math,
finite automata 

0.1, 0.2, 0.5, 0.8 

Closure properties of regular languages, nondeterministic finite automata, regular expressions 



Regular
expressions, 



Review, Exam I, 



Ambiguity
of contextfree grammars, Chomsky normal form 



Fall break, Pushdown automata 



Pumping
lemma for contextfree languages, 



Review, Exam II, 



Nondeterministic
Turing machines, 



Undecidability 



Reducibility 



Review, 



Mapping reducibility, 



Time
complexity, 



NP, 
