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. AddisonWesley, 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: 13 HU: 1.1, 2.12 

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: 46 HU: 2.3 

2/3  regular expressions; converting regular expressions to finite automata and vice versa  K: 79 HU: 2.5 

2/7  Last day to add/change credits  
2/8  Converting finite automata to regular expressions; Kleene algebra  K: 79, 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: 1011 HU: 3.1  
2/11  Last day to register without fee  
2/15  the quotient construction; DFA state minimization; MyhillNerode theorem  K: 1315 HU: 3.4  
2/15  Homework 3 due  
2/17  Coalgebraic approach to automata  Silva thesis, §13 Rutten, §7  
2/22  Brzozowski derivatives  Silva thesis, §3.1.2 Rutten, §8  
2/23  Homework 4 due  
Pushdown Automata and ContextFree Languages  
2/24  2DFAs  K: 1617 HU: 2.6  
2/263/1  February break  
3/3  CFGs and CFLs; rightlinear grammars; Chomsky and Greibach normal forms  K: 1821 HU: 9.1, 4.13,4.56  
3/8  Homework 5 due  
3/8  Pumping lemma for CFLs: formal statement; use in showing sets not contextfree  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: 2325 HU: 5.13  
3/15  Homework 6 due  
3/15  CockeKasamiYounger algorithm; closure properties of CFLs  K: 27 HU: 6.23  
3/17  ChomskySchutzenberger 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  shiftreduce 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.13; 7.6  
4/24/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.45; 7.78  
4/14  universal TMs; diagonalization; undecidability of halting and membership  K: 3032 HU: 8.13  
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.46  
4/25  Homework 9 due  
4/26  other formalisms—while programs; μrecursive functions; λcalculus  K: 3637, 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: 3738  
5/5  Gödel's proof; Gödel's second incompleteness theorem  K: 3738  
5/9  Homework 11 due  
5/10  Final exam review  
5/16  Final exam, 911:30 am, 205 Thurston 