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:
Myhill-Nerode relation, equivalence classes, theorem. Proof that NFA-to-DFA construction can actually require 2^|Q| states. Minimal automata. Proof that automaton constructed in Myhill-Nerode theorem is minimum. NAIVE-MINIMIZE algorithm.

Lecture 10: Thursday, February 4, 2016:
Reintroduction to CFLs. Relationship between CFLs and regular languages. CFGs. PDAs. Group problem solving session 4.

Week 6

Lecture 11: Tuesday, February 9, 2016:
CFGs equivalent to PDAs. Formalization of PDAs. Formalization of CFGs. Informal PDAs allowing no pop, informal CFGs allowing regular expressions. Closure properties of CFLs. Proof of closure over substitution by CFLs. Pumping lemma for CFLs (not proved).

Lecture 12: Thursday, February 11, 2016:
Unary CFLs must be regular. Introduction to Ogden's Lemma. Example 4.3.2. Group problem solving session 5.

Reading Week - No Classes

Week 7

Lecture 13: Tuesday, February 23, 2016:
Ogden's Lemma proof. Ambiguity. Inherent ambiguity.

Lecture 14: Thursday, February 25, 2016:
Parikh's Theorem.

Week 8

Lecture 15: Tuesday, March 1, 2016:
Parikh's Theorem proof. Deterministic Context-Free Languages. Problems with converting PDAs to DPDAs and parsing.

Lecture 16: Thursday, March 3 2016:
Parsing slides

Week 9

Lecture 17: Tuesday, March 8 2016:
Top-down parsing slides

Lecture 18: Thursday, March 10 2016:
Canonical LL(k) slides

Week 10

Lecture 19: Tuesday, March 15 2016:
Bottom-up parsing slides and examples. We also discussed PEG (Parsing Expression Grammars) and Packrat parsing. If PEG is a superset of CFL, then all CFLs can be parsed in linear time, but that is an open problem.

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: