| Week | Topics covered | Notes from Class, and Announcements | Material, Homework, Assignments | ||
|---|---|---|---|---|---|
| Week 1: Jan 6-8 | Course Administrivia; brief overview of the course; Strings, languages, Finite Automata. Regular operations on languages. Non-determinism. |
Overview of course; Academic Integrity
Review; recursive definitions Introducing Finite Automata, ∪ · * Closed and Closure Definition of Computation on FA Regular Languages defn |
Homework: Read Chapter 1 of Maheshwari and Smid; attempt all 8 problems at end of Chapter 1. Do Chapter 2 (p82) Question 1. See the last page of Overview of course; Academic Integrity | ||
| Week 2: Jan 13-15 | Closure of RL under ⋅, ∪, *. Introducing regular expressions. |
DFAs Union NFA intro; converting to DFA RE intro RE identities p56 re to FA conversion |
Problems to work on in FAs and DFAs |
Text howework problems: 2.5, 2.6, 2.11, 2.12, 2.13 | |
| Week 3: Jan 20-22 |
Kleene's Theorem, and the related algorithms Pumping Lemma to prove that a language is not regular. Using closure theorems to help prove a language is not regular. |
Pumping Lemma More pumping lemma |
Assignment 1 Assignment 1 solutions Homework: Text, questions 2.11, 2.12, 2.13, 2.14, 2.15, 2.16, 2.17, 2.18.2, 2.20. |
||
| Week 4: Jan 27-29 |
Introduction to Context Free Languages: Context-free Grammars. Chomsky Normal Form. Intro to PDAs |
Pumping Lemma Problems (Tutorial) P Lemma Closure Thms CFL Intro CFL Continued Chomsky Normal Form (CNF) CFL, PDA |
Exercises: Maheshwari and Smid p133 3.1, (3.2), 3.3, 3.5 Assignment 2 | ||
| Week 5: Feb 3-5 | PDAs; equivalence with CFLs; Top-down and bottom-up parser PDAs. |
PDAs - parser (top down) PDAs - parser (bottom up) Practice on CFGs |
|||
| Week 6: Feb 10-12 |
Some langauges are not Context-Free; Pumping Lemma for CFLs Closure Theorems for CFLs |
Languages that are not Context Free Closure theorems for CFLs |
|||
| Week 7: Feb 17-19 | Study Days | ||||
| Week 8: Feb 24-26 |
Tue: Proving a language is not Context-Free Tue tutorial: Review for Midterm 1 Thu: Midterm 1 |
Counting and Diagonalization |
Sample Test1 - solutions |
||
| Week 9: Mar 3-5 | Countably infinite sets; Uncountability. Intro to Turing Machines |
Tutorial: Enumeration Tutorial: Enumeration and Diagonalization Turing Machine intro TM: multitape, non-det |
|||
| Week 10: Mar 10-12 | TMs: non-determinism, Universal TM, Enumerator TM, Simulating a real computer. |
Non-determinism, Universal TM Enumerator TM (Printer TM) Decidability Decidability and Undecidability |
UC Davis lecture on removing non-determinism See chapter 5 of the textbook |
||
| Week 11: Mar 17-19 |
Tue: Proving languages are undecidable or unrecognizable |
||||
| Week 12: Mar 24-26 |
Thu: Midterm 2 | ||||
| Week 13: Mar 31-Apr 2 |
Tue: Complexity |
||||
| Week 14: Apr 7-9 |
|
||||
| Exam Week: Apr 14-18 | |||||