Lecture Summaries -- Winter 2014

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

Week 1

Lecture 1: Tuesday, January 7, 2014:
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.

Week 2

Lecture 3: Tuesday, January 14, 2014:
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:

Week 3

Lecture 5: Tuesday, January 21, 2014:
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.

Week 4

Lecture 7: Tuesday, January 28 2014:
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 H(L). Introduction to transducers.

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

Week 5

Lecture 9: Tuesday, February 4 2014:
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.

Week 6

Lecture 11: Tuesday, February 11 2014:
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:

Reading Week: February 17-23

Week 7

Lecture 13: Tuesday, February 25 2014:
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.

Week 8

Lecture 15: Tuesday, March 4 2014:
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.

Week 9

Lecture 17: Tuesday, March 11 2014:
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:

A new set of problems to work on in class.

Week 10

Lecture 19: Tuesday, March 18 2014:
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.

Week 11

Lecture 21: Tuesday, March 25 2014: Info about the final exam. Introduction to parsing and recognition problems. The CYK algorithm for CFL recognition. Intro to LR(0) parsing.
Lecture 22: Thursday, March 27 2014: More on LR(0) parsing.

Week 12

Lecture 23: Tuesday, April 1 2014: Turing machines. Unrestricted grammars. Equivalence with TM's. The busy-beaver problem.
Lecture 24: Thursday, April 3 2014: Kolmogorov complexity.