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ć

Introduction to CFL's. Review of PDA, acceptance by empty stack and final state. Review of grammars. Closure properties of CFL's: union, concatenation, star. Non-closure: intersection, complement. Open Problem 13: values of polynomials a context-free language? Closure of CFL's under substitution (by CFL's), morphism, and inverse morphism. Non-closure under quotient.

A new result: if L is finite then ufp(L) (from Problem Set 7 problem 4) is a co-CFL.

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

Lecture 16: Thursday, March 5 2015:

Review of pumping lemma for CFL's. Application: any unary CFL is
actually regular. Introduction to Ogden's lemma.

Group problem solving session: problems.

- Solution to Problem 1 by Mike Stiver

Ogden's lemma. Introduction to Parikh's theorem.

Problem Set 8 available -- due in one week. Solutions to Problem Set 7 available.

Lecture 18: Thursday, March 12 2015:

Another example of Parikh's theorem. Sketch of the proof.
Applications.

Group problem solving session: problems.

- solution to problem 1 by Christopher Hawthorne
- solution to problem 2 by Ilan Ostrovsky
- solution to problem 4 by Stephen Leung

Deterministic context-free languages (DCFL's). Closure under complement. Equivalence classes. Relationship to unambiguous languages. Introduction to parsing and recognition algorithms.

Problem Set 9 available -- due in one week. Solutions to Problem Set 8 available.

Lecture 20: Thursday, March 19 2015:

More about the CYK algorithm. Converting a grammar to Chomsky
normal form in polynomial time. Running time analysis of CYK.
Bottom-up parsing. LR(k) methods. The Knuth DFA.

More about the LR(0) parsing method. Formal definition. The Knuth NFA-epsilon and the Knuth DFA. Proof of correctness. Parsing using the Knuth DFA. Introduction to Kolmogorov complexity.

Problem Set 10 available -- due next Thursday. Solutions to Problem Set 9 available.

Lecture 22: Thursday, March 26 2015: More on Kolmogorov complexity. Formal definition. Applications. The incompressibility method. Getting a lower bound for the number of prime numbers.

Lecture 24: Thursday, April 2 2015: 2DPDA's. Examples of what they can do. Cook's theorem: anything that can be done on a 2DPDA can be done in linear time on a RAM. Awards for the highest average so far and the most errors found in the textbook.