These summaries will be added as the course takes place.

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).

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.

Regular languages, expressions, DFAs, NFAs, epsilon-NFAs. Regular languages closed over substitution, quotient, 1/2, cyclic shift. Proof for quotient.

Lecture 6: Thursday, January 21, 2016:

Proof for 1/2L. Group problem solving session 2.

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.

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.

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.

Ogden's Lemma proof. Ambiguity. Inherent ambiguity.

Lecture 14: Thursday, February 25, 2016:

Parikh's Theorem.

Parikh's Theorem proof. Deterministic Context-Free Languages. Problems with converting PDAs to DPDAs and parsing.

Lecture 16: Thursday, March 3 2016:

Parsing slides

Top-down parsing slides

Lecture 18: Thursday, March 10 2016:

Canonical LL(k) slides

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:

Lecture 22: Thursday, March 24 2016:

Lecture 24: Thursday, March 31 2016: