## 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: