CIS 420/520 Automata Theory, Winter 2002

Details

• Class Times
  • Tuesday/Thursday 8:30-9:50, 248 Gerlinger
• Instructor: David Atkins
  • Office: Deschutes 356, ext 6-4413
  • Office Hours: Tuesday/Thursday 10:30-12:00, Monday/Wednesday 2:00-3:00, and by appointment
  • Email: datkins@cs.uoregon.edu
• Reference Material
  • Required Text: Introduction to the Theory of Computation, by Michael Sipser, PWS Publishing Company, 1997.
  • Other Texts:
    An Introduction to Formal Languages and Automata, by P. Linz, Jones & Bartlett, 2001.
    Introduction to Automata Theory, Languages, and Computing, by J. Hopcroft, R. Motwani, J.Ullman, Addison Wesley, 2001.
    Elements of the Theory of Computation, by H. Lewis and C. Papadimitriou, Prentice Hall, 1998.
    Languages and Machines, by Thomas Sudkamp, Addison Wesley, 1998.
    Theory of Computing - A Gentle Introduction, by E. Kinber and C. Smith, Prentice Hall, 2001.
• Interesting links
  • Alan Turing web site
  • Turing Machine Simulator
  • Finite State Machine Explorer - application to animate automata
• Grading and Policy
  • Approximate weighting: Assignments 15%, Midterm 30%, Final 40%, Other 15% - "Other" will include quizzes and class participation
  • Students registered in 520 will have additional assignment problems and exam problems

Course Objectives

• This course will introduce you to the theoretical basis of computation. In a sense, we will see the origin of the computer as we know it today. We will see mathematical models for computing and how they can be formally described and reasoned about. We will cover the basic models of state machines and Turing machines and see the differences in computational power and how the concept of computing relates to formal languages. We will discuss deterministic and nondeterministic models of machines and how these compare to each other. We will see how the computers and programming we take for granted came from formal reasoning about what computation really is, and understand what computers can and cannot do. We will see Alan Turing's fundamental contributions to computer science. This course provides the basis for more advanced reasoning about algorithms and complexity.
• Have fun gaining an appreciation for what makes computing tick.

Schedule

Assignments

Assignments are due at the beginning of class on the due date indicated. Writing and diagrams must be legible - use machine copy if possible. Work turned in should be your own - if you collaborate with anyone on any of the problems, indicate that on the work you turn in. Academic honesty is expected and cases of suspected dishonesty will be handled according to university policy.

Electronic copy of possible solutions to exercises will not be available, but I will provide a paper copy on request.

Assignment	Topic	Problems	Due
1	Math review	Sipser 0.2, 0.3, 0.4, 0.5, 0.6, 0.11	1/15
2	Deterministic Finite Automata	Sipser 1.1, 1.2, 1.3, 1.4a,b,c,d Additional for CIS 520: Sipser 1.27, 1.29	1/22
3	Nondeterminism	Sipser 1.5a,b,c,f, 1.6a, 1.7a, 1.8b, 1.9, 1.12 Additional for CIS 520: Sipser 1.10, 1.42	1/29
4	Regular Expressions	Sipser 1.13a,b,c,d, 1.14a, 1.15a,b,c, 1.16a Additional for CIS 520: Sipser 1.19, 1.20, 1.21, 1.22	2/5
5	Pumping Lemma	Sipser 1.17a,b Additional for CIS 520: Sipser 1.23a,b, 1.36	2/7
6	Context Free Grammars	Turn in: Sipser 2.4a,c, 2.6a,b, 2.15, 2.19 Additional for CIS 520 to turn in: Sipser 2.25 Recommended (don't turn in):: Sipser 2.1, 2.3, 2.4, 2.6, 2.9	2/21
7	Pushdown Automata	Turn in: Sipser 2.12, 2.13 Additional for CIS 520 to turn in: Sipser 2.26 Recommended (don't turn in): Sipser 2.5, 2.7	2/28
8	Non Context Free Languages	Turn in: Sipser 2.17, 2.18a, 2.21 Recommended (don't turn in): Sipser 2.18b,c,d	3/5
9	Turing Machines	Turn in: Sipser 3.8, 3.14 Additional for CIS 520 to turn in: Sipser 3.13 Recommended (don't turn in): Sipser 3.2, 3.5	3/12

Last updated 2002/03/13 20:18:46