These summaries will be added as the course takes place.

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.

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.

Repetitions in words. Overlaps. Squares. The Thue-Morse sequence

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.

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.

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.

More about the Myhill-Nerode theorem. Proof. Examples. Application: there exist NFA's of

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.

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.

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.

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

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.

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

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