Lecture Summaries -- Winter 2016

These summaries will be added as the course takes place.

Week 1

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

Lecture 2: Thursday, January 7, 2016:
Levi's lemma (2.3.1). The theorems of Lyndon-Schützenberger (2.3.2-2.3.3). Commutativity in a non-commutative setting. Primitive words. Examined but did not yet prove theorem of Fine-Wilf (2.3.5).

Week 2

Lecture 3: Tuesday, January 12, 2016:
Problem Set 1 now available. Theorem 2.3.4. A version of the Fine-Wilf theorem (Theorem 2.3.5). Conjugates. Bordered words. Beginning discussion of morphisms of languages.

Lecture 4: Thursday, January 14, 2016:
Morphisms. Substitutions. Regular languages. Group problem solving session 1.

Week 3

Lecture 5: Tuesday, January 19, 2016:
Regular languages, expressions, DFAs, NFAs, epsilon-NFAs. Regular languages closed over substitution, quotient, 1/2, cyclic shift. Proof for quotient.

Problem Set 2

Lecture 6: Thursday, January 21, 2016:
Proof for 1/2L. Group problem solving session 2.

Week 4

Lecture 7: Tuesday, January 26, 2016:
Transformation automaton. Using transformation automaton to show that pow(L) is regular if L is regular. Boolean matrices. Using boolean matrices to prove that log(L) is regular if L is regular. Moore and Mealy machines.

Lecture 8: Thursday, January 28, 2016:
FSTs. Group problem solving session 3.

Week 5

Lecture 9: Tuesday, February 2, 2016:

Lecture 10: Thursday, February 4, 2016:

Week 6

Lecture 11: Tuesday, February 9, 2016:

Lecture 12: Thursday, February 11, 2016:

Reading Week - No Classes

Week 7

Lecture 13: Tuesday, February 23, 2016:

Lecture 14: Thursday, February 25, 2016:

Week 8

Lecture 15: Tuesday, March 1, 2016:

Lecture 16: Thursday, March 3 2016:

Week 9

Lecture 17: Tuesday, March 8 2016:

Lecture 18: Thursday, March 10 2016:

Week 10

Lecture 19: Tuesday, March 15 2016:

Lecture 20: Thursday, March 17 2016:

Week 11

Lecture 21: Tuesday, March 22 2016:

Lecture 22: Thursday, March 24 2016:

Week 12

Lecture 23: Tuesday, March 29 2016:

Lecture 24: Thursday, March 31 2016: