Website under construction—all information subject to change!
Schedule
All information on this page is subject to change.
Legend: 
handouts 
slides 
code 
video
- K = D. C. Kozen, Automata and Computability, Springer, 1997.
- HU = J. E. Hopcroft, R. Motwani, J. D. Ullman. Introduction to Automata Theory, Languages, and Computation, 3rd ed. Addison-Wesley, 2007.
| DATE | LECTURE/EVENT | READINGS | LINKS |
|---|---|---|---|
| Finite Automata and Regular Sets | |||
| 1/21 | Welcome and introduction; finite alphabets; strings; decision problems; string concatenation; Σ*; length; null string ε; set operations; DFAs; δ^; regular sets | K: 1-3 HU: 1.1, 2.1-2 |
|
| 1/23 | more DFAs; closure properties; the product construction | K: 4 HU: 3.2 |
|
| 1/28 | nondeterminism and NFAs; the subset construction | K: 4-6 HU: 2.3 |
|
| 1/29 | Homework 1 due | ||
| 1/30 | regular expressions; converting regular expressions to finite automata | K: 7-9 HU: 2.5 |
|
| 2/4 | Last day to add/change credits | ||
| 2/4 | Converting finite automata to regular expressions; Kleene algebra | K: 7-9, A HU: 2.5 | |
| 2/5 | Homework 2 due | ||
| 2/6 | Pumping lemma for regular sets: formal statement; use of PL to show nonregularity | K: 10-11 HU: 3.1 | |
| 2/11 | the quotient construction; DFA state minimization; Myhill-Nerode theorem | K: 13-15 HU: 3.4 | |
| 2/12 | Homework 3 due | ||
| 2/13 | Coalgebraic approach to automata | Silva, §1-3 Rutten, §7 | |
| 2/15-2/18 | February break | ||
| 2/20 | Brzozowski derivatives | Silva, §3.1.2 Rutten, §8 | |
| 2/25 | 2DFAs | K: 16-17 HU: 2.6 | |
| 2/26 | Homework 4 due | ||
| Pushdown Automata and Context-Free Languages | |||
| 2/27 | CFGs and CFLs; right-linear grammars; Chomsky and Greibach normal forms | K: 18-21 HU: 9.1, 4.1-3,4.5-6 | |
| 3/4 | Pumping lemma for CFLs: formal statement; use in showing sets not context-free | K: 22 HU: 6.1 | |
| 3/5 | Homework 5 due | ||
| 3/6 | PDAs—formal definition; examples; configurations; acceptance by empty stack and final state; converting NPDAs to CFGs and vice versa | K: 23-25 HU: 5.1-3 | |
| 3/11 | Prelim review | ||
| 3/13 | Prelim (in class) | ||
| 3/18 | Last day to drop/change grading basis | ||
| 3/18 | Cocke-Kasami-Younger algorithm; closure properties of CFLs | K: 27 HU: 6.2-3 | |
| 3/19 | Homework 6 due | ||
| 3/20 | Chomsky-Schutzenberger and Parikh theorems | K: G,H | |
| 3/25 | shift-reduce parsing; operator precedence | K: 26 | |
| 3/26 | Homework 7 due | ||
| General Computability | |||
| 3/27 | general computability; Turing machines; configurations; r.e. and recursive sets; universality; Church's Thesis | K: 28 HU: 7.1-3; 7.6 | |
| 3/29-4/6 | Spring break | ||
| 4/8 | variants of the TM; enumeration machines; nondeterminism; basic properties of recursive and r.e. sets | K: 29, 30 HU: 7.4-5; 7.7-8 | |
| 4/10 | universal TMs; diagonalization; undecidability of halting and membership | K: 30-32 HU: 8.1-3 | |
| 4/15 | reductions—definition and use in showing problems undecidable; Rice's Theorem | K: 33 HU: 8.4 | |
| 4/16 | Homework 8 due | ||
| 4/17 | extended Rice's Theorem; VALCOMPS and undecidable problems for CFLs | K: 34,35 HU: 8.4-6 | |
| 4/22 | other formalisms—while programs; μ-recursive functions; λ-calculus | K: 36-37, I | |
| 4/23 | Homework 9 due | ||
| 4/24 | beyond undecidability | K: J | |
| 4/29 | logic and computation; Gödel's first incompleteness theorem (incompleteness of Peano Arithmetic) | K: 37-38 | |
| 4/30 | Homework 10 due | ||
| 5/1 | Gödel's proof; Gödel's second incompleteness theorem | K: 37-38 | |
| 5/6 | Final exam review | ||
| 5/10-5/17 | Final exam period | ||