Lecture Summaries -- Winter 2017

These summaries will be added as the course takes place.

Week 1

Lecture 1: Wednesday, January 4, 2017:
Information about the course. Marking, exams, Piazza, etc. Course textbook. Course outline. Introduction to combinatorics on words (Chapter 2 of textbook). Basic operations on words: concatenation, reverse, power, perfect shuffle. Basic operations on languages: union, intersection, complement, concatenation. Proofs by induction. The Lyndon-Schutzenberger theorems.

Week 2

Lecture 2: Monday, January 9 2017:
The textbook is still not in the bookstore, but they are promising it soon. In the meantime, there is a copy of the textbook on reserve in the library. More on the Lyndon-Schutzenberger theorems; see the handout. Primitive words. The primitive words problem. I offer an automatic 100 for the course, and $200, for a solution. Introduction to the Fine-Wilf theorem (Theorem 2.3.5). Problem Set 1 is now available.

Lecture 3: Wednesday, January 11 2017:
The textbook is now available. We did Theorem 2.3.5 (the Fine-Wilf theorem). Conjugates. Bordered and unbordered words. Theorem 2.4.2. Theorem 2.4.3: a word is primitive if and only if it has an unbordered conjugate. Problem-solving in small groups, session 1.

Week 3

Lecture 4: Monday, January 16 2017:
Repetitions in words. Overlaps. Squares. The Thue-Morse sequence t. Definition. The sequence t avoids overlaps (we did the alternative proof here). Constructing an infinite word that avoids squares. Properties of the Thue-Morse sequence. (For more about the Thue-Morse sequence, you can read this survey paper or this recent column by James Propp.) Open problem: say something interesting about the lexicographically least squarefree word over the alphabet {0, 1, 2}.

Lecture 5: Wednesday, January 18 2017:
Finite automata and regular languages. Quotient, morphisms, substitutions. Closure of regular languages under these operations. Problem-solving in small groups, session 2.

Week 4

Lecture 6: Monday, January 23 2017:
Inverse morphism. Application to the (general) shuffle product. Theorem 3.3.9: closure of regular languages under inverse morphism. Transducers. Applications of transducers. Formal definition. Problem Set 3 is now available on the course home page.

Lecture 7: Wednesday, January 25 2017:
Finishing up the proof of Nivat's theorem. Nondeterministic versus deterministic transducers. The Kolakoski sequence problem. Problem solving in groups, session 3.

Week 5

Lecture 8: Monday, January 30 2017:
Advanced closure properties of regular languages. Theorem 3.4.3: closure of regular languages under cycle (conjugate). Please read Theorem 3.4.1 and its proof if you haven't seen it before. The transformation automaton. Introduction to use of Boolean matrices. Problem Set 4 now available on course home page.

Lecture 9: Wednesday, February 1 2017:
More on Boolean matrices. Introduction to the Myhill-Nerode theorem. Problem solving in small groups, session 4. Grad students enrolled in 662 should have turned in their project info by now.

Week 6

Lecture 10: Monday, February 6 2017:
More about the Myhill-Nerode theorem. Proof. Examples. Application: there exist NFA's of n states for which the smallest equivalent DFA has exactly 2n states. Introduction to minimization algorithms. Problem Set 5 is now available on the course home page. Open Problem 4: distribution of the number of states resulting from NFA to DFA conversion, followed by minimization.

Lecture 11: Wednesday, February 8 2017:
The Lyngsø-Pedersen conjecture (Open Problem 27). Minimization algorithms for DFA's and applications. Group problem solving, session 5.

Week 7

Lecture 12: Monday, February 13 2017:
Improving the naive algorithm for DFA minimization. Applications.

Lecture 13: Wednesday, February 15 2017:
The subsequence and subword orderings. Antichains (sets of pairwise incomparable elements). The subsequence ordering has no infinite antichains. Minimal elements. The set of minimal elements of a language is finite. Regularity of sup(L) and sub(L). Group problem solving, session 6.

Reading week, February 20 and 22

Week 8

Lecture 14: Monday, February 27 2017:
Context-free languages: review. Definition of context-free grammar. Chomsky normal form. The pumping lemma for CFL's: the 4-minute proof. Review of pushdown automata: acceptance by empty stack and final state. Closure properties of the class of CFL's: closed under union, concatenation, star, but not intersection or complement. Closure of CFL's under morphism and substitution (by CFL's). Closure of CFL's under inverse morphism and transduction.

Lecture 15: Wednesday, March 1 2017:
Every unary CFL is actually regular (pdf). CFL's are not closed under quotient. Group problem solving, session 7.

Week 9

Lecture 16: Monday, March 6 2017: Ogden's lemma and its applications. Lemma 4.3.1 and Theorem 4.4.1. Open problem 8 on the list.

Lecture 17: Wednesday, March 8 2017: Parikh's theorem: introduction. Group problem solving, session 8.

Week 10

Lecture 18: Monday, March 13 2017: Proof of Parikh's theorem. Introduction to parsing and recognition algorithms for CFL's.

Lecture 19: Wednesday, March 15 2017: The CYK algorithm: parsing and recognition. Introduction to LR(0) parsing: handle, viable prefix, item, valid item, complete item. The Knuth NFA and the Knuth DFA.

Week 11

Lecture 20: Monday, March 20 2017: Proving the correctness of the Knuth DFA. Introduction to Turing machines. Unrestricted grammars. Open Problem 28.

Lecture 21: Wednesday, March 22 2017: Introduction to Kolmogorov complexity.

Week 12

Lecture 22: Monday, March 27 2017: Conclusion to Kolmogorov complexity. The incompressibility method.

Lecture 23: Wednesday, March 29 2017: Unsolvable problems dealing with CFL's. Information about the take-home final.

Week 13

Lecture 24: Monday, April 3 2017: Last class! 2DPDA's. Awards for highest average so far, and for the person who found the most errors in the text.