## Lecture Summaries -- Winter 2020

These summaries will be added as the course takes place.

### Week 1

• Lecture 1, Monday, January 6 2020: Course information. Outline of the course. Strings (aka words), both finite and infinite. Prefix, suffix, subword, subsequence. Reversal of a word. Palindromes. Theorem: a word of length n contains, as subwords, at most n+1 distinct palindromes (including the empty word). (Can you find the proof?) Words with few palindromes. Powers of a word. Primitive words. Open problem #1: primitive words. You get an automatic 100 for the course for solving any open problem. The theorems of Lyndon and Schützenberger. Proof of Theorem 2.3.2.

Textbook reading for Lecture 1: review Chapter 1, brushing up on anything not familiar to you. Read sections 2.1-2.3.

• Lecture 2, Wednesday, January 8 2019. The course textbook 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 of 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! The Fine-Wilf theorem.

### Week 2

• Lecture 3, Monday, January 13 2020. Finished the proof of Theorem 2.4.3. Introduction to avoidability in words. Open Problem 3: say something interesting about the lexicographically least infinite word over {0,1,2} avoiding squares. Proof of Theorems 2.5.1 and 2.5.2 (we used the alternate proof of Theorem 2.5.1 on the course web page). Section 2.6.2. Open Problem 2.

Textbook reading: sections 2.3, 2.4, 2.5, 2.6.

• Lecture 4, Wednesday, January 15 2020. Fractional powers. Theorem 2.3.6. More about the Thue-Morse word. Sections 2.6.1, 2.6.3. Problem solving in small groups with group set #1.

### Week 3

• Lecture 5, Monday, January 20 2020: Review of finite automata and regular language. Closure operations. Quotient. Morphisms and substitutions. Closure under substitution. Closure under inverse morphism. Definition of shuffle. Here is a handout on the shuffle operation that gives a bit more information than what is in the text. Open Problem 30 the number of length-2n binary strings arising from self-shuffling.

Solutions to Problem Set 1 are available on LEARN.

• Lecture 6, Wednesday, January 22 2020: Solution to the problem of (general) shuffle using morphisms and inverse morphisms (Example 3.3.8). Transducers. Statement of Nivat's theorem. Open Problem 23 on transducers and the Thue-Morse sequence. Problem solving in small groups with group set #2.

### Week 4

• Lecture 7, Monday, January 27 2020: Proof of Nivat's theorem. The "cyc" operation on languages. The operation (1/2)L on languages. Introduction to the transformation automaton. Reading: Sections 3.4, 3.5, beginning of Section 3.7.

Solutions to Problem Set 2 are available on LEARN.

• Lecture 8, Wednesday, January 29 2020: Proof of the properties of the transformation automaton (Theorem 3.7.1, 3.7.2, Corollary 3.7.3). Example 3.7.5. Introduction to section 3.8. Problems solving in small groups with group set #3. I mentioned Open Problem #8.

### Week 5

• Lecture 9, Monday, February 3 2020: Open problem #22: distinguishing strings with DFA's. More discussion of the boolean matrix approach to automata theory. Introduction to the Myhill-Nerode theorem. Reading: Sections 3.8 and 3.9 of the textbook.

Solutions to Problem Set 3 are available on LEARN.

• Lecture 10, Wednesday, February 5 2020: Proof of the Myhill-Nerode theorem. Proof of uniqueness of minimal automata. Problems solving in small groups with group set #4.

### Week 6

• Lecture 11, Monday, February 10 2020: Applications of the Myhill-Nerode theorem. State complexity. Max blowup going from NFA to DFA. Minimization algorithms. Reading: textbook, sections 3.9-3.11.

Solutions to Problem Set 4 are available on LEARN.

• Lecture 12, Wednesday, February 12 2020: Brzozowski's amazing algorithm for DFA minimization. State complexity of intersection of languages. Problem solving in small groups with group set 5.

### Week 7

• Lecture 13, Monday, February 24 2020: Partial orders, sub and sup operations, minimal elements. Review of context-free languages. Closure of the class of CFL's under substitution (by CFL).

• Lecture 14, Wednesday, February 26 2020: Closure of the class of CFL's under inverse morphism. Every unary CFL is regular. Problem solving in small groups with group set 6.

### Week 8

• Lecture 15, Monday, March 2 2020: Ogden's lemma. Reason why we need it. Examples. Proof. Applications: proof of existence of inherently ambiguous languages. Introduction to Parikh's theorem.

• Lecture 16, Wednesday, March 4 2020: More on Parikh's theorem. Examples of how to use it to prove a language not CF. Problem solving in small groups with group set 7.

### Week 9

• Lecture 17, Monday, March 9 2020: Proof of Parikh's theorem. DPDA's and DCFL's. The class DCFL is closed under complement. Example of a DCFL.

• Lecture 18, Wednesday, March 11 2020: Proof of Theorem 4.7.4. Problem solving in small groups with group set 8 (last one).

### Week 10

Cancelled because of coronavirus.

### Week 11

• Lecture 19, Monday, March 23 2020: Introduction to parsing and recognition algorithms for CFL's. The Cocke-Younger-Kasami algorithm. LR(0) parsing.

Slides for this lecture. Video is on LEARN.

• Lecture 20, Wednesday, March 25 2020: More on LR(0) parsing. Intro to Kolmogorov complexity. Video is on LEARN.

### Week 12

• Lecture 21, Monday, March 30 2020: More about Kolmogorov complexity. Unsolvable problems about CFL's. Video is on LEARN.

• Lecture 22, Wednesday, April 1 2020: More about unsolvable problems. 2DPDA's and Cook's theorem. Slides. Award for the highest average so far. Video is on LEARN.