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:

Week 8

Lecture 15: Tuesday, March 3, 2015:
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.

Week 9

Lecture 17: Tuesday, March 10 2015:
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.

Week 10

Lecture 19: Tuesday, March 17 2015:
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.

Week 11

Lecture 21: Tuesday, March 24 2015:
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.

Week 12

Lecture 23: Tuesday, March 31 2015: more on Kolmogorov complexity. The invariance theorem. How Kolmogorov complexity changes as x increases in length. The incompressibility method applied to regular languages. Unsolvable problems related to CFL's. The Turing machine model. Theorem 6.6.2 and Corollary 6.6.4.

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.