Lecture Summaries -- Winter 2018

These summaries will be added as the course takes place.

Week 1

Lecture 1: Wednesday, January 3 2018: Course information. Outline of the course. Strings (aka words), both finite and infinite. Reversal of a word. Palindromes. Theorem: a word of length n contains, as subwords, at most n+1 distinct palindromes. (Can you find the proof?) Words with few palindromes. Powers of a word. Morphisms. Iterated morphisms. Open problems on words (problems 14 and 29). You get an automatic 100 for the course for solving any open problem. The theorems of Lyndon and Schutzenberger. Proof of Theorem 2.3.2.

Week 2

Lecture 2: January 8 2018. Course textbook is available in the bookstore. It is the basic reference for all material in the course, but there will be occasional supplements from time to time. The textbook has some errata, which are available on the errata page. Please report all NEW errata you find to the instructor (no matter how trivial). (Check the errata page to see if it's new.)

Lecture summaries of each lecture are available on the course home page.

One handout is on the course home page, the alternative proof to Theorem 2.3.3. We will only do "Second proof of..." in today's class (last class we proved Theorem 2.3.2). Motivation for Theorem 2.3.3: it says when words commute. This is a big theme in mathematics. For example, there is a theorem that says that two diagonalizable matrices M and M' commute if and only if they are simultaneously diagonalizable. (Diagonalizable means that there is a matrix A such that A M A-1 is a diagonal matrix; simultaneously diagonalizable means that the same A works for both M and M'. More motivation for that theorem: when does mi = nj have solutions for positive integers m, n ≥ 2?

Theorems 2.3.4 and 2.3.5. The "primitive words" are sort of an analogy for the prime numbers in number theory. They are still mysterious! See open problem # 1 on the open problems page. Introduction to the Fine-Wilf theorem.

Lecture 3: January 10 2018. The Fine-Wilf theorem (Theorem 2.3.5). Conjugates. Borders. Theorems 2.4.1, 2.4.2, and 2.4.3. Group problem-solving session #1.

Week 3

Lecture 4: January 15 2018. Repetitions in words. Overlaps. Squares. The Thue-Morse sequence t. Definition. The sequence t avoids overlaps, Theorem 2.5.1 (but we did the alternative proof here). Constructing an infinite word that avoids squares (Theore 2.5.2). Properties of the Thue-Morse sequence (section 2.6.3). (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: January 17 2018. More about the Thue-Morse sequence. We covered sections 2.6.1, 2.6.2 of the course textbook. An open problem, Open Problem 9: additive squares.

Problem solving in small groups, Group Problems #2.

Week 4

Lecture 6: Monday, January 22 2018. Introduction to advanced properties of regular languages. Two themes: closure properties (what can we do to a regular language and have it still be regular?) and state complexity (how many states are needed to express a given regular language?)

Quotients (Section 3.2). Theorem 3.2.3: If R is regular and L is any language, then R/L is regular. Morphisms. Substitutions. Theorem 3.3.5: the class of regular languages is closed under substitution (by regular languages). Inverse morphisms. Theorem 3.3.9: the class of regular languages is closed under inverse morphisms. Definition of shuffle. Here is a handout on the shuffle operation that gives a bit more information than what is in the text.

Lecture 7: Wednesday, January 24 2018. A cool open problem on regular languages! (Problem 26). Closure of the regular languages under reverse. Theorem 3.4.1 (closure of the regular languages under the operation ½). Theorem 3.4.3 (closure of the regular languages under the operation of cyclic shift).

Problem solving in small groups. Group Problems #3.

Week 5

Lecture 8: Monday, January 29 2018. Another great open problem on automata: the separating words problem (Problem 22). Transducers. Example of a transducer: compute the base-2 expansion of n+1 from the base-2 expansion of n. Nivat's theorem (Theorem 3.5.3). Another open problem on automata: the Endrullis-Hendriks transducer problem. Introduction to the transformation automaton.

Lecture 9: Wednesday, January 31 2018. More about the transformation automaton. Theorems 3.7.1, 3.7.2 and Crollary 3.7.3. Illustration of Example 3.7.5. Introduction to automata and matrices (Section 3.8).

Problem solving in small groups. Group Problems #4.

Week 6

Lecture 10: Monday February 5 2018. More on the matrix approach to DFA's and NFA's. Theorem 3.8.6. Proposition 3.8.8. Introduction to the Myhill-Nerode theore (Section 3.9). Relations. Equivalence relations. Equivalence classes: notation, properties. Notion of "index" (number of equivalence classes). Right-invariance of equivalence relations on Σ*. The equivalence relation RM based on a DFA M. The Myhill-Nerode equivalence relation RL based on a language L. Statement of the theorem. Example.

Avoid this common error: these equivalence relations are used to compare all strings of Σ*, not just those in L or L(M).

Lecture 11: Wednesday February 7 2018. Proof of the Myhill-Nerode theorem (Theorem 3.9.5). Example: the Myhill-Nerode equivalence class for { 0n 1n : n ≥ 0 }. Application: example of an n-state NFA for which the smallest equivalent DFA has 2n states.

Problem solving in small groups. Group Problems #5.

Week 7

Lecture 12: Monday, February 12 2018. Uniqueness of minimal DFA. Minimization of DFA. Theorem 3.10.1, Theorem 3.10.2, Theorem 3.10.3, Corollary 3.10.4, Theorem 3.10.5, Theorem 3.10.7.

Lecture 13: Wednesday, Febrary 14 2018. Brzozowski's minimization algorithm (Theorem 3.10.8). Intro to state complexity (Theorems 3.11.1, 3.11.2).

Problem solving in small groups. Group Problems #6.

Reading week, February 19-23

Have a good break!

Week 8

Lecture 14: Monday, February 26 2018. Cancelled due to illness of instructor. Sorry.

Lecture 15: Wednesday, February 28 2018. Guest lecture by Jonathan Buss. Theorems 3.11.3, 3.11.4, and 3.11.5. Section 3.12. Definitions of partial order, subword and subsequence. Theorem 3.12.1. Lemma 3.12.4. Theorem 3.12.5.

Week 9

Lecture 16: Monday, March 5 2018. Context-free languages, review: definition of context-free grammar, derivations, etc. Pushdown automata: definition, etc. Theorem 4.2.1: unary CFL's are regular. (I gave a different exposition of the proof.) Closure of CFL's under substitution (by CFL's), inverse morphism, finite-state transduction.

Lecture 17: Wednesday, March 7 2018. Ogden's lemma (Lemma 4.3.1). Application to proving languages not context-free. Inherently ambiguous languages. Proof that a certain specific CFL is inherently ambiguous (Theorem 4.4.1).

Week 10

Lecture 18: Monday, March 12 2018. Linear and semilinear sets. Examples. Theorem 4.6.3. The "super pumping lemma" (Lemma 4.6.4). Parikh's theorem (Theorem 4.6.5).

Lecture 19: Wednesday March 14 2018. Applications of Parikh's theorem. Example 4.6.6. Introduction to DCFL's. The class of DCFL's closed under complement (Theorem 4.7.2). Example 4.7.3.

Problem solving in small groups: Group Problems #7.

Week 11

Lecture 20: Monday, March 19 2018. More on DCFL's. Theorem 4.7.4. Introduction to parsing and recognition algorithms for CFL's. The CYK algorithm. Complexity considerations. Introduction to LR methods.

Lecture 21: Wednesday, March 21 2018. The LR(0) parsing method. Definition of right sentential form, item, complete item, handle, viable prefix, valid for viable prefix. Examples. The Knuth NFA-ε and the Knuth DFA. Problem solving in small groups: Group Problems #8.

Week 12

Lecture 22: Monday, March 26 2018. Proof of correctness of the Knuth DFA. LR(0) parsing using the Knuth DFA.

Lecture 23: Wednesday, March 28 2018. Turing machines. Recall of the model. Kolmogorov complexity.

Week 13

Lecture 24: Monday, April 2 2018. Last lecture. Prize for the highest average so far. Prize for the most errata found in course textbook.

Note: Wednesday April 4 2018 is actually on a Friday schedule, so there is no class on that day.