Lecture Summaries -- Winter 2012

Week 1

Lecture 1: Wednesday, January 4, 2012:
I handed out the Course information sheet. Problem Set 1 is available and due January 11. 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).

Week 2

Lecture 2: Monday, January 9, 2012:
Second theorem of Lyndon-Schützenberger (Theorem 2.3.3). Primitive words. Theorem 2.3.4. Introduction to a version of the Fine-Wilf theorem (Theorem 2.3.5). Open problem #1: is the set of primitive words over {0, 1} context-free?

Herb Wilf was a combinatorialist at the University of Pennsylvania who just recently passed away.

Lecture 3: Wednesday, January 11, 2012:
Problem Set 2 is available and due January 18. Theorem 2.3.6. Definitions of conjugates and bordered words. Theorems 2.4.2 and 2.4.3, Lemma 2.4.4, Theorem 2.4.5.

Solutions to Problem Set 1 are available, but you need a username and password that will be distributed on Monday, January 16 (or contact the instructor or TA).

Week 3

Lecture 4: Monday, January 16, 2012:
We covered Theorem 2.5.1, but with a different proof from the textbook's. You can find the alternate proof here. We also did Theorem 2.5.2 and covered parts of Sections 2.6.2 and 2.6.3.

Open problem #3: What are the properties of the lexicographically least squarefree word?

Lecture 5: Wednesday, January 18, 2012:
We covered the remaining material in Section 2.6. We also began Chapter 3, covering the material in Section 3.2.

Problem Set 1 (marked) was returned. Problem Set 3 is now available on the course home page, and the solutions to Problem Set 2 are there.

Open problem #9: Is there an infinite word over a finite subset of N with no two consecutive blocks of the same size and the same sum?

Week 4

Lecture 6: Monday, January 23 2012: We discussed applications of morphisms and substitutions. Examples 3.3.6, 3.3.7, 3.3.8. Proof that regular languages are closed under taking inverse morphism (Theorem 3.3.9). Automata with output. We briefly convered section 3.1 (read proofs on your own). We started section 3.5, and sketched the beginning of the proof of Theorem 3.5.3.

Lecture 7: Wednesday, January 25 2012: The Kolakoski word: an open problem about transducers. More on transducers: sketch of the proof of Nivat's theorem. The operation cyc(L) and proof that if L is regular, then so is cyc(L). Introduction to 2DFA's.

Problem Set 4 is available from the course home page, and the solutions to Problem Set 3 are available, too.

Week 5

Lecture 8: Monday, January 30 2012: We gave a formal definition of 2DFA's, and a formal definition of acceptance based on configurations. We discussed the simulation of 2DFA's by DFA's.

We introduced the transformation automaton, and showed how it could be used to accept T(L), where L is a regular language and T is the map T(L) = { x : x* ⊆ L }.

Lecture 9: Wednesday, February 1 2012: Automata and boolean matrices. Section 3.8. Introduction to the Myhill-Nerode theorem (p. 77).

Open problem: show how to find all the strings accepted by an n-state unary acyclic NFA in O(n2) time.

Week 6

Lecture 10: Monday, February 6, 2012: The Myhill-Nerode theorem. Section 3.9.

Lecture 11: Wednesday, February 8 2012: Minimization of finite automata. Section 3.10.

Problem Set 6 is available from the course home page, and the solutions to Problem Set 5 are available, too.

Week 7

Lecture 12: Monday, February 13 2012: Brzozowski's algorithm. Proof of correctness (Theorem 3.10.8). State complexity (section 3.11).

I mentioned two open problems: Number 7 on the list is to determine good upper and lower bounds on the worst-case state complexity of (c(L*))*. Here by c(A) I mean the complement of A.

The second (Number 5 on the list) is to determine the distribution of state sizes in the minimal dfa for the reversed language LR, where L is accepted by an n-state DFA.

Lecture 13: Wednesday, February 15 2012: Partial orders and regular languages: section 3.12 of the textbook.

Two open problems: Number 5: Does every power of 16 greater than 164 have a digit 1, 2, 4, or 8 when written in base 10?

Number 12: Is there a prime of the form 8 · 134i + 183 for i ≥ 1? Resolving this would allow a classification of the minimal elements of the primes expressed in base 13.

Update: Curtis Bright has found a "probably prime" for i = 8005.

Problem Set 7 is available from the course home page. It is due on February 29, so you have two weeks to do it. The solutions to Problem Set 6 are available.

Week 8: No class (reading week)

No class, no office hours, no virtual office hours.

Week 9

Lecture 14: Monday, February 27 2012: introduction to CFL's. Reminder of the conventions for PDA's. Proof that the class of CFL's is closed under morphism, substitution, and inverse morphism. Proof that every unary CFL is regular. Intro to Ogden's lemma.

Open problem: let p be a polynomial of degree ≥ 2 such that p(N) ⊆ N. Let k be an integer ≥ 2. Prove or disprove: for all such p and k, { (p(n))k : n ≥ 0 } is not a CFL.

Lecture 15: Wednesday, February 29 2012: proof of Ogden's lemma. Ambiguity of context-free grammars. Inherent ambiguity of context-free languages. Proof of inherent ambiguity of a language.

Problem Set 8 is available from the course home page. It is due on March 7. The solutions to Problem Set 7 are available.

Week 10

Lecture 16: Monday, March 5, 2012: Parikh's theorem. Statement. Examples. Proof. Applications to proving a language not context-free.

Lecture 17: Wednesday, March 7 2012: More about Parikh's theorem. The interchange lemma.

Week 11

Monday, March 12, 2012: No class because Prof. Shallit is away.

Lecture 18: Wednesday, March 14, 2012: Shuo Tan will give a guest lecture on non-closure of CFL's under quotient, and deterministic context-free languages.

Week 12

Lecture 19: Monday, March 19, 2012: Introduction to parsing and recognition algorithms.

Lecture 20: Wednesday, March 21 2012: LR(0) parsing. The Knuth NFA and DFA. Using the Knuth DFA to parse.

Week 13

Lecture 21: Monday, March 26, 2012: Finished up with LR(0) parsing. Proof of correctness. Introduction to 2DPDA's.

Lecture 22: Wednesday, March 28 2012: More on 2DPDA's. Sketch of simulation. The Chomsky hierarchy. Context-sensitive grammars. Length-increasing grammars. Unrestricted grammars.

Week 14

Lecture 23: Monday, April 2, 2012: Kolmogorov complexity. Basic definitions. Incomputability. The incompressibility method.