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 will go 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 will also go over the definitions in Sections 2.1 and 2.2. We will prove the first theorem of Lyndon-Schützenberger (Theorem 2.3.2).

Lecture 2: Thursday, January 9, 2014:

Second theorem of Lyndon-Schützenberger (Theorem 2.3.3).
Commutativity in a non-commutative setting.
Primitive words.
Open problem #1: is the set of primitive
words over
{0, 1} context-free?

Problem Session #1.

- Version A
- solution to problem A-1 by Kevin McDormand

- Version B
- solution to problem B-1 by Nancy Iskander

- Version C

Theorem 2.3.4. A version of the Fine-Wilf theorem (Theorem 2.3.5). Theorem 2.3.6. Conjugates. Bordered words. Theorems 2.4.1 through 2.4.5.

Lecture 4: Thursday, January 16, 2014:

Introduction to repetitions in strings.
The Thue-Morse word. Avoiding overlaps.
Proof that it is overlap-free.

Problem Solving Session 2 (still working on problems from previous week). Solutions:

- Solution to problem C-1 by Alex Mueller
- Solution to problem A-3 by Christina Skublics:
- Solution to problem A-2 by Grant Baltare:
- wk1-c3.pdf by Devin Papineau

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); group theory (the Burnside problem), number theory, and so forth. Open Problem #3: lexicographically least squarefree word.

Lecture 6: Thursday, January 23, 2014:

Construction of a squarefree word from the Thue-Morse word.
Closure of regular languages under quotient. Nonconstructive
nature of the construction.

Problem Session #3, using new problems.

- solution to problem A-1 by Nancy Iskander
- solution to problem B-1 by Oliver Grant
- solution to problem B-2 by Christina Skublics
- solution to problem C-1 by Marc Burns
- solution to problem C-2 by Marc Burns
- solution to problem C-3 by Sean Hunt

More about closure properties of regular languages. Applications of quotient to the problem of removing leading and trailing zeros. Morphism, inverse morphism, substitution. Closure of regular languages under each of these operations. The ("ordinary" or not necessarily perfect) shuffle operation. Lecture 8: Thursday, January 30 2014:

Application of morphism to the (ordinary) shuffle operation. If two languages are regular, so are their shuffle. More advanced closure properties: the case of

We continued working on the problems from the previous problem-solving session.

- Solution to problem B-3, Xun Edison Wang

Proof of Nivat's theorem. Introduction to 2DFA's.

For next time, read section 3.9 and 3.10 of the text.

Lecture 10: Thursday, February 6 2014: Open Problem #10: The Kolakoski problem. Open Problem #23: The Thue-Morse transducer problem. Proof of the theorem on 2DFA's.

Problem-Solving Session: a new set of problems.

- Solution to A-1 by Namgil Lee
- Solution to C-1 by Devin Papineau

The transformation automaton. Applications. Automata and boolean matrices. Applications.

Lecture 12: Thursday, February 13 2014:

More on automata and boolean matrices. Open problem #22:
distinguishing
strings with automata.
Open problem #11: determining
all the strings accepted by a unary acyclic NFA.

Problem Solving Session:

- Solution to B-2 by Abel Nieto Rodriguez
- Solution to C-2 and B-1 by Kevin McDormand
- Solution to A-2 by Marc Burns

Introduction to the Myhill-Nerode theorem. Applications.

Lecture 14: Thursday, February 27 2014:

Minimization of automata. The "naive" minimization algorithm.
Here is a revised version of the proof of
Theorem 3.10.2 from the text. The version I had was a bit sloppy.

Problem-Solving Session: a new set of problems.

- Solution to problem B-1 by Nathan Arnold
- Solution to problem A-1 by Fang-Ying Chu
- Solution to problem B-2 by Michael Park

More about minimization. Improving the minimization algorithm to run in quadratic time. Application to shortest string distinguishing two DFA's that accept different languages. Brzozowski's algorithm for minimization. Definitions of the sub and sup operators on languages. Minimal elements.

Lecture 16: Thursday, March 6 2014:
More about minimal elements, and the operations sup and sub.
Proof that every set of pairwise incomparable elements is finite.
Proof that sup(L) and sub(L) are regular.

A new set of problems to work on in class.

- Solution to problem B-1 by Nancy Iskander
- Solution to problem B-2 by Jeff Lyons

Intro to advanced properties of context-free languages: closure under substitution, morphism, and inverse morphism. Proof that if L is a CFL, and R is regular, then L/R is a CFL. I also gave an improved proof of Theorem 4.2.1: a unary language is a CFL iff it is regular.

Lecture 18: Thursday, March 13 2014:

Ogden's lemma. Two open problems:

- Open problem #1: is the set of primitive words a CFL?
- Open problem #13: is
the set of base-
*k*representations of the values of polynomials of degree ≥2 a CFL?

A new set of problems to work on in class.

- Solution to A-1 by Christina Skublics
- Solution to C-1 by Nancy Iskander

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

Lecture 20: Thursday, March 20 2014:
Proof of Parikh's theorem.

A new set of problems to work on in class.

- Solution to problem 1 by Gregory Cole

Lecture 22: Thursday, March 27 2014: More on LR(0) parsing.

Lecture 24: Thursday, April 3 2014: Kolmogorov complexity.