Lecture notes are intended only to show what topics were covered, so you can find and read the corresponding sections in the textbook. They are not intended to be a substitute for the textbook and handouts.
| Lecture Number | Date | Material covered | Lecture notes | Lecture screen capture | Readings/Handouts/Hyperlinks | Comments |
|---|---|---|---|---|---|---|
| 1 | 1/20 | Administrivia, overview, motivation | lecture 1 | slides#1 | Chapter 0 | |
| disc 1 | 1/20,21 | Discrete math review intro to strings |
discussion 1 | Chapter 0 Extra notes: Discrete Mathematics, by Chen Read Chap. 1, 2 and 3 (20 pgs). | ||
| 2 | 1/22 | Strings and languages intro to DFAs |
Lecture 2 | slides#2 | Section 1.1 | |
| 3 | 1/27 | JFLAP demo formal definitions for DFAs closure under complement |
Lecture 3 | slides#3 | Section 1.1 JFLAP |
|
| disc 2 | 1/27,28 | DFA examples | discussion 2 | Section 1.1 | ||
| 4 | 1/29 |
formal proof of product construction closure under union, intersection regular expressions |
lecture 4 | slides#4 | Sections 1.1, 1.3 | |
| 5 | 2/3 | NFA's | lecture 5 | slides#5 | Section 1.2 | |
| disc 3 | 2/3,4 | NFA examples | discussion 3 | Section 1.2 | ||
| 6 | 2/5 |
closure under three regular operations string reversal; regex to NFA | lecture 6 | slides#6 | Sections 1.2, 1.3
closure properties |
7 | 2/10 | Equivalence of NFA's and DFA's | lecture 7 | slides#7 | Section 1.2 |
| disc 4 | 2/10,11 |
Subset construction Epsilon transitions |
Section 1.2 | |||
| 8 | 2/12 | Regular expressions equivalent to NFAs/DFAs | lecture 8 | slides#8 | Section 1.3 | Monday is Valentine's day |
| 9 | 2/17 | Proving languages non-regular | lecture 9 | Whiteboard lecture no slides |
Section 1.4
pumping lemma help |
|
| disc 5 | 2/17,18 | Pumping lemma examples | discussion 5 | Section 1.4 | ||
| 10 | 2/19 | Suffix languages DFA minimization |
lecture 10 | slides#10 | [see lecture notes] | |
| 2/24 | First midterm 7-9pm lecture = review |
7pm-9pm, 151 Loomis, 1110 West Green Street, Urbana. | ||||
| disc 6 | 2/24,25 | Proofs using closure properties | ||||
| 11 | 2/26 | Context-free grammars, parse trees, ambiguity | lecture 11 | slides#11 | Section 2.1
The Groke grammar example Green Eggs and Ham |
|
| 12 | 3/3 | Chomsky normal form | lecture 12 | Section 2.2
Sheila Greibach (picture) Noam Chomsky 1965 computer |
||
| disc 7 | 3/3,4 | Context-free grammar | discussion 7 | |||
| 13 | 3/5 | CNF effectiveness, and closure properties |
lecture 13 | slides#13 | Section 2.2
closure properties |
|
| 14 | 3/10 | Pumping Lemma for CFLs, Non-context-free languages, Nonclosure of CFLs under intersection. | lecture 14 | slides#14 | ||
| disc 8 | 3/10,11 | CFGs | discussion 8 | |||
| 15 | 3/12 | Non-closure of CFLs under complement; closure under homomorphism; CYK membership algorithm; Recursive automata | lecture 15 |
slides#15 | Recursive Automata Notes |
Friday might be drop date ?????? |
| 16 | 3/17 | Equivalence of CFGs and RAs; closure constructions on RA; pushdown automata | lecture 16 | slides#16 | St. Patrick's Day | |
| disc 9 | 3/17,18 | CFGs, recursive automata | ||||
| 17 | 3/19 | Turing machines | lecture 17 | slides#17 | Section 3.1 Alan Turing Alonzo Church |
|
| 3/24 | Fighting and waiting through crowded airports | Spring break | ||||
| 3/26 | Playing in the sun having fun | Spring break |
||||
| 18 | 3/31 |
More TM examples Multi-tape TMs |
lecture 18 | Section 3.2 | ||
| disc 10 | 3/31,4/1 | Preparing for the second midterm | ||||
| 4/2 | Second midterm 7-9pm lecture = review |
|||||
| 19 | 4/7 | Encoding problems, decidability | lecture 19 | Section 3.3, 4.1 | ||
| disc 11 | 4/7,8 | TM design examples | discussion 11 | Friday is Good Friday | ||
| 20 | 4/9 |
TM as interpreter, simulating a real computer, more decidable problems |
lecture 20 | LOST! Computer crash! | Section 4.1 | Passover |
| 21 | 4/14 | The Halting Problem and Undecidability | lecture 21 | slides#21 | Section 4.2 | |
| disc 12 | 4/14,15 | Help! The Halting problem blew out my brain! | discussion 12 | |||
| 22 | 4/16 | Reductions for undecidability | lecture 22 | slides#22 | Section 5.1 reduction help |
|
| 23 | 4/21 | Rice's Theorem | lecture 23 | slides#23 | Section 5.1 | |
| disc 13 | 4/21,22 | Examples of reductions | discussion 13 | |||
| 24 | 4/23 |
Dovetailing Enumeration and recognizability Non-deterministic TM's |
lecture 24 | No slides | Sections 5.1 | |
| 25 | 4/28 |
Undecidable problems for linear bounded TMs and CFLs |
lecture 25 | slides#25 | Section 3.2 | |
| disc 14 | 4/28,29 | Dovetailing | discussion 14 | |||
| 26 | 4/30 | Complexity theory; P vs NP; Cook-Levin Theorem |
No lecture notes; See Sipser | slides#26 | Sipser Chapter 7 | |
| 27 | 5/5 | Recap and review session | Review handout | |||
| disc 15 | 5/5 | Review for final | discussion 15 | |||
| 5/6 | reading day: no class | |||||
| 5/7 | exam week: no class | |||||
| 5/12 | exam week: no class |
