These summaries are tentative and will be updated as the course takes place.

I will hand out the course information sheet. Slide: formal languages and connections to other areas. We went over the basic definitions of concepts such as word (string), language, reversal, power, palindrome, empty string, prefix, suffix, subword, etc. (pages 1-4 of the course textbook). We also went over the definitions in Sections 2.1 and 2.2. We proved the first theorem of Lyndon-Schützenberger (Theorem 2.3.2). I mentioned Open Problem #1.

Lecture 2: Thursday, January 8, 2015:

Second theorem of Lyndon-Schützenberger (Theorem 2.3.3).
Commutativity in a non-commutative setting.
Primitive words. First problem-solving session in small groups.
List of problems. Solutions:

Problem Set 1 now available. Theorem 2.3.4. A version of the Fine-Wilf theorem (Theorem 2.3.5). Theorem 2.3.6. Conjugates. Bordered words.

Lecture 4: Thursday, January 15, 2015:

Theorem 2.4.3 and Theorem 2.4.5. (Please read the proof of Lemma 2.4.4, which
we did not do.) Second problem-solving session in small groups.
List of problems. Solutions:

- Problem 1, by Chris Hawthorne
- Problem 2, by Ford Peprah
- Problem 3, by Marianna Rapoport
- Problem 4, by Siwei Yang
- Problem 5, by Mike Stiver

Section 3.5 of the text. Avoiding patterns in words. Thue's theorem on avoiding overlaps and squares. I used these alternative notes that the Thue-Morse word

Problem Set 2
available. Solutions to Problem Set 1
available.

Lecture 6: Thursday, January 22, 2015:

Open Problem #3: lexicographically
least squarefree word.

Introduction to languages and regular languages. If R is regular and L is any language, then R/L is regular.

Group problem-solving #3. List of problems. Solutions:

- Problem 1, by Ming-Ho Yee
- Problem 2, by Andrew Patterson
- Problem 4, by Bernard Mak (and also see Open Problem #8: separation of CFL's !).

Morphisms. Substitutions. Inverse morphisms. Writing shuffle in terms of morphism and inverse morphism (and intersection). Regular languages closed under morphism, substitution, and inverse morphism. The operation ½(

Problem Set 3 available. Solutions to Problem Set 2 available.

Lecture 8: Thursday, January 29, 2015:

More about ½(*L*). Theorem 3.4.3: If *L* is regular,
so is cyc(*L*). Some material that's not in the text:
borders and regular languages.

Group problem-solving #4.
List of problems.
Solutions:

TA Chen Fei Du lectured because Prof. Shallit was away. Finite state transducers (FST's). Informal definition, Example 3.5.1, formal definition, transduction of strings and languages. Using transducers to compute morphisms and inverse morphisms. Composition of transducers (Theorem 3.5.6). Nivat's theorem (Theorem 3.5.3). Finite-state transducers on infinite words. The Kolakoski word. Degrees of streams. Open Problem 10 and Open Problem 23.

Problem Set 4 available. Solutions to Problem Set 3 available.

Lecture 10: Thursday, February 5, 2015:

The matrix approach to automata. Using the matrix approach
to show that if L is regular, then so is log(L) (Proposition 3.8.8).

Group problem-solving #5.
List of problems.
Solutions:

One more application of the matrix approach: efficiently listing the strings accepted by a unary NFA. Naive approach runs in cubic time; this is improved in Theorem 3.8.5. Open Problem 11: improve the running time in that theorem. The Myhill-Nerode theorem. Relations. Equivalence relations. Right-invariance. Index.

Problem Set 5 available -- due in two weeks! Solutions to Problem Set 4 available.

Lecture 12: Thursday, February 12, 2015:

More applications of Myhill-Nerode: theorem gives unique minimal
DFA for a regular language. Another application: proving existence of NFA's
of n states for which minimal equivalent DFA has
2^{n} states.

Group problem-solving #6.
List of problems.
Solutions:

Open problem 23: distinguishing strings with automata.

Minimizing finite automata. The NAIVE-MINIMIZE and MINIMIZE algorithms. Correctness. Running times. Applications (Theorem 3.10.5).

Problem Set 6 available -- due in one week. Solutions to Problem Set 5 available.

Lecture 14: Thursday, February 26, 2015:

Brzozowski's algorithm for DFA minimization. State complexity.

Group problem-solving #7.
List of problems.
Solutions:

- Problem 1 by Uroš Dimitrijević