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 | lec | tut | |
|---|---|---|---|---|---|
| 1 | Sep 1 | Introduction, finite automata | §1, 2.2 | ppt | |
| 2 | Sep 5 | Nondeterministic finite automata | §2.3 | ppt | |
| 3 | Sep 8 | Regular expressions | §2.5, 3 | ppt | ppt |
| 4 | Sep 12 | Properties of regular languages | §4.2 | ppt | |
| Sep 15 | No class, mid-autumn festival | ppt | |||
| 5 | Sep 19 | Limitations of finite automata | §4.1 | ppt | |
| 6 | Sep 22 | DFA minimization | §4.4.3 | ppt | |
| 7 | Sep 26 | More on DFA minimization and equivalence | §4.4.2, 4.4.4 | ppt | |
| 8 | Sep 29 | Context-free languages, parsing | §5.1, 5.2, 5.4 | ppt | |
| 9 | Oct 3 | Normal forms, parsing algorithms | §7.1, 7.4.4 | ppt | |
| 10 | Oct 6 | Pushdown automata | §6.1, 6.3 | ppt | ppt |
| 11 | Oct 10 | Limitations of PDAs | §7.2 | ppt mp3 | |
| 12 | Oct 13 | Parsers for programming languages | ppt mp3 | ||
| 13 | Oct 17 | Midterm review | ppt | ||
| Oct 20 | Midterm exam | ppt | |||
| 14 | Oct 24 | LR(k) parsers | ppt mp3 | ||
| 15 | Oct 27 | The Church-Turing thesis | §8.1, 8.2 | ppt mp3 | |
| 16 | Oct 31 | Variants of Turing Machines | §8.3, 8.4, 8.6 | ppt mp3 | |
| 17 | Nov 3 | Undecidability | §9.1, 9.2 | ppt | |
| 18 | Nov 7 | More undecidable problems | §9.3 (-9.3.3) | ppt | |
| 19 | Nov 10 | Undecidable problems about CFGs | §9.4, 9.5 | ppt | |
| 20 | Nov 14 | Efficient Turing Machines | ppt mp3 | ||
| 21 | Nov 17 | Polynomial time, P and NP | §10.1 | ppt mp3 | ppt |
| 22 | Nov 21 | Reductions, the Cook-Levin Theorem | §10.1.5, 10.2 | ppt mp3 | |
| 23 | Nov 24 | NP-complete problems | §10.2-10.4 | ppt mp3 | |
| 24 | Nov 28 | Interaction and zero-knowledge | ppt | ||
| 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.