CS541 AUTOMATA THEORY
FALL 2001


Lecturer: James F. Lynch
Office: SC-381
Telephone: 268-2374
email: jlynch@clarkson.edu
Office hours: MWF 9:30AM-11: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 three exams and the final.

Three hourly exams:

70%

Final:

30%

Hourly exam dates:

Wednesday, September 19

 

Wednesday, October 17

 

Wednesday, November 14


SYLLABUS


Week of


Topics


Text


Exercises and Problems

August

27

Basic math, finite automata



Ch. 0 & 1.1

0.1, 0.2, 0.5, 0.8
1.1, 1.2, 1,3. 1.4 a., e., f., k.

September

3

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


Ch. 1.2 & 1.3

 

10

Regular expressions,
pumping lemma for regular languages


Ch. 1.3 & 1.4

 


17

Review,

Exam I,
Context-free grammars


Ch. 2.1

 


24

Ambiguity of context-free grammars, Chomsky normal form


Ch. 2.1

 

October

1

Fall break,

Pushdown automata


Ch. 2.2

 


8

Pumping lemma for context-free languages,
Turing machines


Ch. 2.3, 3.1

 


15

Review,

Exam II,
Turing machines


Ch. 3.2

 


22

Nondeterministic Turing machines,
algorithms, decidability


Ch. 3.2. 3.3. 4.1

 


29

Undecidability



Ch. 4.2

 

November

5

Reducibility



Ch. 5.1, 5.2

 


12

Review,
Exam III,
mapping reducibility


Ch. 5.3

 


19

Mapping reducibility,
Thanksgiving


Ch. 5.3

 


26

Time complexity,
P and NP


Ch. 7.17.3

 

December

3

NP,
Review


Ch. 7.4