CS345 AUTOMATA THEORY
FALL 2004


Lecturer: James F. Lynch
Office: SC-381
Telephone: 268-2374
email: 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


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

     


October         4

     


                    11

     


                    18

     


                    25

     


November      1

     


                      8

     


                    15

     


                    22

     


                    19