These summaries will be added as the course takes place.

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

- Solution to #3 by A. A.-S.
- Solution to #4 by G. B.
- Solution to #6 by T. F. L. (= Group problem solving session #2, problem 5).
- Solution to #7 by K. S.

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.

- Solution to #1 by J. W. V. S.
- Solution to #3 by A. J.
- Solution to #6 by Y. T. Z.

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.

- Solution to #2 by L. Y.
- Solution to #5 by A. M. L.
- Solution to #7 by A. M. L.

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.

- Solution to #1 by E. K.
- Solution to #3 by J. M.
- Solution to #6 by A. B.
- Solution to #7 by M. R.

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 { 0^{n} 1^{n} : n ≥ 0 }. Application: example of
an *n*-state NFA for which the smallest equivalent
DFA has 2^{n} states.

Problem solving in small groups. Group Problems #5.

- Solution to #4 by N. W.
- Solution to #6 by K. H. D.

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.

- Solution to #3 by T. F. L.
- Solution to #6 by W. G.

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.

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

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.

- Solution to #1 by R. Z.
- Solution to #5 by M. S.

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.

- Solution to #6 by D. C.
- Solution to #7 by E. G. S.

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

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