CS154 Spring 2020 Lecture Notes

Formal Languages and Computability

Videos of lectures are available.

Below are my lecture notes for the class so far. They should serve as a rough guide to what was covered on any given day. Frequently, however, I say more in class than is in these notes. Also, I tend to dynamically correct typos on the board that might appear in these lecture notes. So caveat emptor.

Week 1: [Jan 27 - Automata Theory and Computability] [Jan 29 - Sets, Relations, Graphs]

Week 2: [Feb 3 - More Sets, Functions, Graphs] [Feb 5 - More Graphs, Proofs, and Finite Automata]

Week 3: [Feb 10 - Deterministic Finite Automata] [Feb 12 - Designing DFAs - Product Construction]

Week 4: [Feb 17 - NFAs, Minimization] [Feb 19 - Finish Minimization]

Week 5: [Feb 24 - Regular Expressions] [Feb 26 - Regular Expressions from NFAs - Grammars]

Week 6: [Mar 2 - Star-Height - Homomorphism - Quotients - Pumping Lemma] [Mar 4 - Pumping Lemma - Context-Free Grammars]

Week 7: [Mar 9 - Practice Midterm Day] [Mar 11 - Midterm]

Week 8: [Mar 16 - Creating Grammars - Dealing with Ambiguity] [Mar 18 - Chomsky Normal Form]

Week 9: [Mar 23 - Parsing CFGs] [Mar 25 - Greibach Normal Form - PDAs]

Week 10: [Mar 30 - Spring Break] [Apr 1 - Spring Break]

Week 11: [Apr 6 - PDAs and CFLs, Pumping Lemma for CFLs] [Apr 8 - CFL Closures and CFL Algorithms, TMs]

Week 12: [Apr 13 - Working with Turing Machines] [Apr 15 - Equivalents of Turing Machine Variants]

Week 13: [Apr 20 - More Turing Machine Variants] [Apr 22 - Finish Rams, Nondeterministic TMs]

Week 14: [Apr 27 - UTMs, Diagonalization] [Apr 29 - Hierarchy Theorems, co-r.e. sets, Reductions]

Week 15: [May 4 - Computation Histories] [May 6 - PCP, Rice's Theorem]