CIS 420/520 Automata Theory

Fall 2006 Syllabus

[ CIS 420/520 Home Page | Assignments | Announcements ] Last updated 2006/11/29 10:37:40

      Week       Topic Reading
Week 1
9/25 - 9/29
  • Introduction and Overview
  • Math notation and Proofs
  • Intro to Finite Automata
Sipser, Chapter 0
Sipser, Section 1.1
Selected lecture notes
Week 2
10/2 - 10/6
  • Regular Languages
  • Nondeterminism
Sipser, Section 1.2
Selected lecture notes
Week 3
10/9 - 10/13
  • DFA/NFA Equivalence
  • Regular Operations
Sipser, Section 1.2
Selected lecture notes
Week 4
10/16 - 10/20
  • Regular Expressions
  • Pumping Lemma
Sipser, Sections 1.3, 1.4
Selected lecture notes
Week 5
10/13 - 10/27
  • Midterm review
Sipser, Chapter 1
Notes on state minimization
Midterm Exam Friday, October 27
Week 6
10/30 - 11/3
  • Context-free Grammars
  • Chomsky Normal Form
  • Pushdown Automata
Sipser, Sections 2.1, 2.2
Selected lecture notes
Week 7
11/6 - 11/10
  • PDA/CFL Equivalence
  • Pumping Lemma for CFLs
Sipser, Sections 2.2, 2.3
Selected lecture notes
Week 8
11/13 - 11/17
  • Turing Machines
  • Turing Machine Variants
Sipser, Sections 3.1, 3.2
Selected lecture notes
Week 9
11/20 - 11/22
  • Decidability
  • Halting Problem
Sipser, Sections 3.3, 4.1, 4.2
Week 10
11/27 - 12/1
  • Reducibility
  • Review
Sipser, Sections 5.1, 5.2
Final review questions
Final Exam Wednesday, December 6, 3:15 PM