These summaries will be added as the course takes place.

- 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 m^{i}= n^{j}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.

Problem Set 1 is now available on the course home page.

- 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.

- 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.

- 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.

- 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.

- 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.

- 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.

- 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.

- 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).

- 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.

Information about the final exam

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

- 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.