Syllabus


This outline follows closely the chapters in the textbook. We will have a few side excursions to topics in parsing, the lambda calculus and LISP, and cryptography. It is likely that some of the topics will spill over into more than one lecture, in which case the midterm will be moved accordingly.

Lecture 1: HIstorical introduction. Mathematical review: sets, sequences, operations on sets, strings, mathematical proofs.

Lecture 2: Finite-state machines and regular languages.

Lecture 3: Applications of deterministic finite-state automata: lexical scanning in programming languages. Non-deterministic FSA.

Lecture 4: Regular expressions and their relationship to FSA.

Lecture 5: Non-regular languages. The pumping lemma for regular languages.

Lecture 6: quiz on the above (chapter 1 of text).

Lecture 7: Context-free grammars. Parse trees, derivations.

Lecture 8: Pushdown automata and parsers.

Lecture 9: Equivalence of PDAs and CFGs.

Lecture 10: Predictive parsing, FIRST and FOLLOW functions.

Lecture 11: Deterministic and non-deterministic grammars. Ambiguity and the Cocke-Kasami-Young parsing algorithm. Complexity of parsing.

Lecture 12: midterm examination (comprehensive).

Lecture 13: Turing Machines. Definition, alternative models, robustness.

Lecture 14: Recursive and recursively enumerable sets. Diagonalization.

Lecture 15: Decidability. Decidable problems on languages.

Lecture 16: The halting problem.

Lecture 17: Reducibility.

Lecture 18: The recursion theorem

Lecture 19: Information complexity.

Lecture 20: Complexity. Review of big-O notation, algorithm analysis. The class O.

Lecture 21: The class NP. Certificates, verification.

Lecture 22: NP-completeness: the Cook-Levin theorem.

Lecture 23: NP-complete problems: vertex cover, graph coloring, etc. Application to register allocation.