CS345 AUTOMATA THEORY
FALL 2004


Lecturer: James F. Lynch
Office: SC-381
Telephone: 268-2374
E-mail: jlynch@clarkson.edu
Office hours: MWF 11:00AM-11:30AM, 2:00PM-3:30PM
Lecture hours: MWF 1:00PM-1:50PM Snell Hall 213
Text: Introduction to the Theory of Computation, by Michael Sipser


OBJECTIVES

We will cover Chapters 0-5 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 quizzes, three exams and the final.  Quizzes will be scheduled at the end of each Friday class, except when specifically cancelled.  They will be based on exercises and problems assigned for that week.

Quizzes:

10%

Three hourly exams:

60%

Final:

30%

Hourly exam dates:

Wednesday, September 15

Wednesday, October 13

Wednesday, November 10


SYLLABUS

Week of

Topics

Text

Exercises and Problems/B>

August
23

Basic math

Ch. 0

0.1, 0.2, 0.4, 0.8
Solutions

30

Finite automata

Ch. 1.1, 1.2

1.1, 1.2, 1,3. 1.4 a., e., f., k.
Solutions

September
6

Nondeterministic finite automata,
regular languages


Ch.1.2, 1.3

1.5 a., 1.7 a., 1.12, 1.13, 1.14, 1.30
(not for Friday’s quiz, but for Exam I:
1.17 b., 1.23 a., c., 1.36) Solutions

13

   

(no quiz this Friday)

20

     

27

     

4

     

11

     

18

     

25

     

November      1

     

8

     

15

     

22

     

19