CIS 420/520 Automata Theory, Spring 2002

CRN 35575/35576

[ Details | Objectives | Schedule | Assignments ]

Last updated 2002/06/05 14:22:09

Details


Course Objectives


Schedule

Week Topic Reading
Week 1, 4/2-4
  • Introduction and Overview
  • Math notation and Proofs
  • Intro to Finite Automata
Sipser, Chapter 0
Sipser, Section 1.1
Selected lecture notes
Week 2, 4/9-11
  • Regular Languages
  • Nondeterminism
Sipser, Section 1.2
Selected lecture notes
Week 3, 4/16-18
  • DFA/NFA Equivalence
  • Regular Operations
Sipser, Section 1.2
Selected lecture notes
Week 4, 4/23-25
  • Regular Expressions
  • Pumping Lemma
Sipser, Sections 1.3, 1.4
Selected lecture notes
Week 5, 4/30-5/2
  • Midterm review
  • Midterm Exam Thursday, May 2
Sipser, Chapter 1
Selected lecture notes
Week 6, 5/7-9
  • Context-free Grammars
  • Chomsky Normal Form
  • Pushdown Automata
Sipser, Sections 2.1, 2.2
Selected lecture notes
Week 7, 5/14-16
  • PDA/CFL Equivalence
  • Pumping Lemma for CFLs
Sipser, Sections 2.2, 2.3
Selected lecture notes
Week 8, 5/21-23
  • Turing Machines
  • Turing Machine Variants
Sipser, Sections 3.1, 3.2
Selected lecture notes
Week 9, 5/28-30
  • Decidability
  • Halting Problem
Sipser, Sections 3.3, 4.1, 4.2
Week 10, 6/4-6
  • Reducibility
  • Review
Sipser, Sections 5.1, 5.2
Selected lecture notes
Final Exam 8 AM Thursday, June 13


Assignments

Working diligently on the assignments is key to understanding the material in this course. Often it is not until you attempt to write down a formal description, diagram, or proof that you really "get" a concept.

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. In particular, copying someone else's work (including material found on the web) will not be tolerated. If solutions to assignments are obtained from outside sources, the source must be cited.

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 Deterministic Finite Automata Turn in: Sipser 1.4a,b,c,d, 1.29
Additional for CIS 520 to turn in: Sipser 1.26
Recommended (don't turn in): Sipser 1.1, 1.2, 1.3
4/11
2 Nondeterminism Turn in: Sipser 1.5a,b,c,f, 1.10, 1.11
Additional for CIS 520 to turn in: Sipser 1.42
Recommended (don't turn in): Sipser 1.6, 1.7, 1.8, 1.9, 1.12
4/18
3 Regular Expressions, Pumping Lemma Sipser 1.16a, 1.23a,b, 1.36
Additional for CIS 520: Sipser 1.41
Recommended (don't turn in): Sipser 1.13, 1.14, 1.15, 1.17
4/30
4 Context Free Grammars Turn in: Sipser 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.9
5/14
5 Pushdown Automata, Non CFLs Turn in: Sipser 2.13, 2.17, 2.18d, 2.26
Additional for CIS 520 to turn in: Sipser 2.27
Recommended (don't turn in): Sipser 2.5, 2.7, 2.12, 2.18a,b,c
5/23
6 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
5/30
7 Decidability Turn in: Sipser 4.3, 4.10, 4.12
Additional for CIS 520 to turn in: Sipser 4.13
6/6


datkins@cs.uoregon.edu

Last updated 2002/06/05 14:22:09