This schedule will be updated periodically throughout the term. Last update: June 23
Readings and, in some cases, web-links are given for each of the topics listed below. Readings are from the course text unless otherwise noted.
Text: Introduction to Automata Theory, Languages, and Computation (2nd or 3rd Edition) by John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman.
|
Date |
Topic |
Reading |
|---|---|---|
|
May 19 |
Introduction |
Chapter 1 |
|
May 20 |
Deterministic Finite Automata |
2.1-2 |
|
May 21 |
Nondeterministic Finite Automata |
2.3-4 |
|
May 22 |
Finite Automata with Epsilon-Transitions |
2.5 |
|
May 23 |
Regular Expressions and Finite Automata |
3.1-2 |
|
May 26 |
No class; Memorial Day |
|
|
May 27 |
Algebraic Laws for Regular Expressions |
3.3-4 |
|
May 28 |
The Pumping Lemma & Closure Properties |
4.1-2 |
|
May 29 |
Closure Properties & Decision Properties of Regular Languages |
4.2-3 |
|
May 30 |
Equivalence & Minimization of Automata |
4.4 |
|
June 2 |
Context Free Grammars |
5.1 |
|
June 3 |
Parsing |
5.2-4 |
|
June 4 |
Pushdown Automata |
6.1-2 |
|
June 5 |
Equivalence of PDAs and CFGs |
6.3 |
|
June 6 |
Midterm (in class) |
|
|
June 9 |
Deterministic Pushdown Automata (DPDAs) |
6.4 |
|
June 10 |
Normal Forms for Context Free Grammars |
7.1 |
|
June 11 |
Pumping Lemma for CFGs |
7.2 |
|
June 12 |
Closure Properties of Context Free Languages |
7.3 |
|
June 13 |
Decision Properties of CFLs |
7.4 |
|
June 16 |
Introduction to Turing Machines |
8.1-2 |
|
June 17 |
Turing Machine Extensions |
8.4 |
|
June 18 |
Restricted Turing Machine |
8.5 |
|
June 19 |
Recursive Sets & Recursively Enumerable Sets |
9.1 |
|
June 20 |
Undecidable Problems |
9.2 |
|
June 23 |
Undecidable Problems & Rice's Theorem |
9.3 |
|
June 24 |
More Undecidable Problems |
9.4 |
|
June 25 |
Intractable Problems: P vs. NP |
10.1-2 |
|
June 26 |
Course Review |
|
|
June 27 |
Final Exam |
|