Lecture Summaries -- Winter 2015

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

Week 1

Lecture 1: Tuesday, January 6, 2015:
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:

Week 2

Lecture 3: Tuesday, January 13, 2015:
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:

Week 3

Lecture 5: Tuesday, January 20, 2015:
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 t is overlap-free, not the course text proof. Various places that the Thue-Morse word and squarefree words appears in the literature: in music (music of Per Nørgård); chess (the German rule of Max Euwe). Open Problem #9: avoiding additive squares.

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:

Week 4

Lecture 7: Tuesday, January 27, 2015:
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 ½(L).

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:

Week 5

Lecture 9: Tuesday, February 3, 2015:
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:

Week 6

Lecture 11: Tuesday, February 10, 2015:
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 2n states.

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

Reading Week - No Classes

Week 7

Lecture 13: Tuesday, February 24, 2015:
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: