Lecture Summaries -- Winter 2016
These summaries will be added as the course takes place.
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).
Lecture 3: Tuesday, January 12, 2016:
Problem Set 1 now available.
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.
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.
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.
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
Lecture 10: Thursday, February 4, 2016:
Reintroduction to CFLs. Relationship between CFLs and regular languages. CFGs.
PDAs. Group problem solving session 4.
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
Lecture 13: Tuesday, February 23, 2016:
Ogden's Lemma proof. Ambiguity. Inherent ambiguity.
Lecture 14: Thursday, February 25, 2016:
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:
Lecture 17: Tuesday, March 8 2016:
Top-down parsing slides
Lecture 18: Thursday, March 10 2016:
Canonical LL(k) slides
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:
Lecture 21: Tuesday, March 22 2016:
Lecture 22: Thursday, March 24 2016:
Lecture 23: Tuesday, March 29 2016:
Lecture 24: Thursday, March 31 2016: