| 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 More pumping lemma problems More pumping lemma problems |
Assignment 1 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 | Pumping Lemma to prove that a language is not regular. Using closure theorems to help prove a language is not regular. |
Pumping Lemma Problems (Tutorial) |
|||
| Week 5: Feb 3-5 | Introduction to Context Free Languages: Context-free Grammars. Ambiguous grammars. | ||||
| Week 6: Feb 10-12 |
CFG: Proving that a given grammar generates a particular language.
Intro to PDAs |
||||
| Week 7: Feb 17-19 | Study Days | ||||
| Week 8: Feb 24-26 |
Tue: Proving a language is not Context-Free Thu: Midterm 1 |
||||
| Week 9: Mar 3-5 | Countably infinite sets; Uncountability. Intro to Turing Machines | ||||
| Week 10: Mar 10-12 | Turing Machines, cont'd. | ||||
| Week 11: Mar 17-19 | TMs: non-determinism, Universal TM, Enumerator TM, Simulating a real computer. | ||||
| Week 12: Mar 24-26 |
Tue: Proving languages are undecidable or unrecognizable Thu: Midterm 2 | ||||
| Week 13: Mar 31-Apr 2 |
Tue: Complexity |
||||
| Week 14: Apr 7-9 |
|
||||
| Exam Week: Apr 14-18 | |||||