Schedule
All information on this page is subject to change.
Permanent Zoom link: https://cornell.zoom.us/j/93585746762?pwd=TTJTNUY0b21IbUM0bVJDUnBMcC9BQT09
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/25 | 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/27 | more DFAs; closure properties; the product construction | K: 4 HU: 3.2 |
|
| 2/1 | Homework 1 due | ||
| 2/1 | nondeterminism and NFAs; the subset construction | K: 4-6 HU: 2.3 |
|
| 2/3 | regular expressions; converting regular expressions to finite automata and vice versa | K: 7-9 HU: 2.5 |
|
| 2/7 | Last day to add/change credits | ||
| 2/8 | Converting finite automata to regular expressions; Kleene algebra | K: 7-9, A HU: 2.5 | |
| 2/9 | Homework 2 due | ||
| 2/10 | Pumping lemma for regular sets: formal statement; use of PL to show nonregularity | K: 10-11 HU: 3.1 | |
| 2/11 | Last day to register without fee | ||
| 2/15 | the quotient construction; DFA state minimization; Myhill-Nerode theorem | K: 13-15 HU: 3.4 | |
| 2/15 | Homework 3 due | ||
| 2/17 | Coalgebraic approach to automata | Silva thesis, §1-3 Rutten, §7 | |
| 2/22 | Brzozowski derivatives | Silva thesis, §3.1.2 Rutten, §8 | |
| 2/23 | Homework 4 due | ||
| Pushdown Automata and Context-Free Languages | |||
| 2/24 | 2DFAs | K: 16-17 HU: 2.6 | |
| 2/26-3/1 | February break | ||
| 3/3 | CFGs and CFLs; right-linear grammars; Chomsky and Greibach normal forms | K: 18-21 HU: 9.1, 4.1-3,4.5-6 | |
| 3/8 | Homework 5 due | ||
| 3/8 | Pumping lemma for CFLs: formal statement; use in showing sets not context-free | K: 22 HU: 6.1 | |
| 3/10 | 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/15 | Homework 6 due | ||
| 3/15 | Cocke-Kasami-Younger algorithm; closure properties of CFLs | K: 27 HU: 6.2-3 | |
| 3/17 | Chomsky-Schutzenberger and Parikh theorems | K: G,H | |
| 3/21 | Last day to drop/change grading basis | ||
| 3/21 | Homework 7 due | ||
| 3/22 | Prelim review | ||
| 3/24 | Prelim (in class) | ||
| 3/29 | shift-reduce parsing; operator precedence | K: 26 | |
| General Computability | |||
| 3/31 | general computability; Turing machines; configurations; r.e. and recursive sets; universality; Church's Thesis | K: 28 HU: 7.1-3; 7.6 | |
| 4/2-4/10 | Spring break | ||
| 4/12 | 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/14 | universal TMs; diagonalization; undecidability of halting and membership | K: 30-32 HU: 8.1-3 | |
| 4/18 | Homework 8 due | ||
| 4/19 | reductions—definition and use in showing problems undecidable; Rice's Theorem | K: 33 HU: 8.4 | |
| 4/21 | extended Rice's Theorem; VALCOMPS and undecidable problems for CFLs | K: 34,35 HU: 8.4-6 | |
| 4/25 | Homework 9 due | ||
| 4/26 | other formalisms—while programs; μ-recursive functions; λ-calculus | K: 36-37, I | |
| 4/28 | beyond undecidability | K: J | |
| 5/2 | Homework 10 due | ||
| 5/3 | logic and computation; Gödel's first incompleteness theorem (incompleteness of Peano Arithmetic) | K: 37-38 | |
| 5/5 | Gödel's proof; Gödel's second incompleteness theorem | K: 37-38 | |
| 5/9 | Homework 11 due | ||
| 5/10 | Final exam review | ||
| 5/16 | Final exam, 9-11:30 am, 205 Thurston | ||