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 nonregular  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 79pm lecture = review 
7pm9pm, 151 Loomis, 1110 West Green Street, Urbana.  
disc 6  2/24,25  Proofs using closure properties  
11  2/26  Contextfree 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  Contextfree 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, Noncontextfree languages, Nonclosure of CFLs under intersection.  lecture 14  slides#14  
disc 8  3/10,11  CFGs  discussion 8  
15  3/12  Nonclosure 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 Multitape TMs 
lecture 18  Section 3.2  
disc 10  3/31,4/1  Preparing for the second midterm  
4/2  Second midterm 79pm 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 Nondeterministic 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; CookLevin 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 