CIS 420/520 Automata Theory

Fall 2007 Syllabus

[ CIS 420/520 Home Page | Assignments | Announcements ] Last updated 2007/11/25 22:22:04

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