# Schedule

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.

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/1nondeterminism and NFAs; the subset constructionK: 4-6
HU: 2.3
2/3regular expressions; converting regular expressions to finite automata and vice versaK: 7-9
HU: 2.5
2/7 Last day to add/change credits
2/8Converting finite automata to regular expressions; Kleene algebraK: 7-9, A
HU: 2.5
2/9 Homework 2 due
2/10Pumping lemma for regular sets: formal statement; use of PL to show nonregularityK: 10-11
HU: 3.1
2/11 Last day to register without fee
2/15the quotient construction; DFA state minimization; Myhill-Nerode theoremK: 13-15
HU: 3.4
2/15 Homework 3 due
2/17Coalgebraic approach to automataSilva thesis, §1-3
Rutten, §7
2/22Brzozowski derivativesSilva thesis, §3.1.2
Rutten, §8
2/23 Homework 4 due
Pushdown Automata and Context-Free Languages
HU: 2.6
2/26-3/1 February break
3/3CFGs and CFLs; right-linear grammars; Chomsky and Greibach normal formsK: 18-21
HU: 9.1, 4.1-3,4.5-6
3/8 Homework 5 due
3/8Pumping lemma for CFLs: formal statement; use in showing sets not context-freeK: 22
HU: 6.1
3/10PDAs—formal definition; examples; configurations; acceptance by empty stack and final state; converting NPDAs to CFGs and vice versaK: 23-25
HU: 5.1-3
3/15 Homework 6 due
3/15Cocke-Kasami-Younger algorithm; closure properties of CFLsK: 27
HU: 6.2-3
3/17Chomsky-Schutzenberger and Parikh theoremsK: G,H
3/21 Last day to drop/change grading basis
3/21 Homework 7 due
3/22Prelim review
3/24Prelim (in class)
3/29shift-reduce parsing; operator precedenceK: 26
General Computability
3/31general computability; Turing machines; configurations; r.e. and recursive sets; universality; Church's ThesisK: 28
HU: 7.1-3; 7.6
4/2-4/10 Spring break
4/12variants of the TM; enumeration machines; nondeterminism; basic properties of recursive and r.e. setsK: 29, 30
HU: 7.4-5; 7.7-8
4/14universal TMs; diagonalization; undecidability of halting and membershipK: 30-32
HU: 8.1-3
4/18 Homework 8 due
4/19reductions—definition and use in showing problems undecidable; Rice's TheoremK: 33
HU: 8.4
4/21extended Rice's Theorem; VALCOMPS and undecidable problems for CFLsK: 34,35
HU: 8.4-6
4/25 Homework 9 due
4/26other formalisms—while programs; μ-recursive functions; λ-calculusK: 36-37, I
4/28beyond undecidabilityK: J
5/2 Homework 10 due
5/3logic and computation; Gödel's first incompleteness theorem (incompleteness of Peano Arithmetic)K: 37-38
5/5Gödel's proof; Gödel's second incompleteness theoremK: 37-38
5/9 Homework 11 due
5/10Final exam review
5/16 Final exam, 9-11:30 am, 205 Thurston