Automata theory is the study of abstract computational devices. The purpose of this course is to understand the power and limitations of such devices via rigorous methods. We will study various models including finite automata, grammars, pushdown automata, and Turing machines.
We will develop methods for classifying computational devices according to their computational power, and tools which will allow us to tell if a device is powerful enough to solve a given computational problem.
| date | topic | readings | |
|---|---|---|---|
| 1 | Sep 1 | Introduction, finite automata | §1, 2.2 |
| 2 | Sep 5 | Nondeterministic finite automata | §2.3 |
| 3 | Sep 8 | Regular expressions | §2.5, 3 |
| 4 | Sep 12 | Properties of regular languages | §4.2 |
| Sep 15 | No class, mid-autumn festival | ||
| 5 | Sep 19 | Limitations of finite automata | §4.1 |
| 6 | Sep 22 | DFA minimization | §4.4.3 |
| 7 | Sep 26 | More on DFA minimization and equivalence | §4.4.2, 4.4.4 |
| 8 | Sep 29 | Context-free languages, parsing | §5.1, 5.2, 5.4 |
| 9 | Oct 3 | Normal forms, parsing algorithms | §7.1, 7.4.4 |
| 10 | Oct 6 | Pushdown automata | §6.1, 6.3 |
| 11 | Oct 10 | Limitations of PDAs | §7.2 |
| 12 | Oct 13 | Parsers for programming languages | |
| 13 | Oct 17 | Midterm review | |
| Oct 20 | Midterm exam | ||
| 14 | Oct 24 | LR(k) parsers | |
| 15 | Oct 27 | The Church-Turing thesis | §8.1, 8.2 |
| 16 | Oct 31 | Variants of Turing Machines | §8.3, 8.4, 8.6 |
| 17 | Nov 3 | Undecidability | §9.1, 9.2 |
| 18 | Nov 7 | More undecidable problems | §9.3 (-9.3.3) |
| 19 | Nov 10 | Undecidable problems about CFGs | §9.4, 9.5 |
| 20 | Nov 14 | Efficient Turing Machines | |
| 21 | Nov 17 | Polynomial time, P and NP | §10.1 |
| 22 | Nov 21 | Reductions, the Cook-Levin Theorem | §10.1.5, 10.2 |
| 23 | Nov 24 | NP-complete problems | §10.2-10.4 |
| 24 | Nov 28 | Interaction and zero-knowledge | |
| Dec 10 | Final exam |
Homeworks will be issued on Mondays every other week and will be due within 10 days. You are encouraged to collaborate on them, but you must write up your own solutions and list your collaborators on the solution sheet.