Week  Date  Topic  Readings  Posted Materials  

1  Jan. 10  Course Overview  Review Chapter 0  Slides  
Jan. 12  Finite Automata  Section 1.1, pages 3140  Notes, exercises, answers  
Jan. 14  Definition of Regular Languages  Section 1.1, pages 4044  Notes, delta*, exercises, answers  
2  Jan. 17  Martin Luther King Jr. Birthday  
Jan. 19  Properties of Regular Languages  Section 1.1, pages 4447  Notes, exercises, answers  
Jan. 21  Nondeterminism  Section 1.2, pages 4754  Notes, exercises, answers, quiz 1, answers  
3  Jan. 24  Relation Between NFAs and DFAs  Section 1.2, pages 5463  Notes, exercises, answers, closure under concatenation and Kleene closure  
Jan. 26  Regular Expressions  Section 1.3, pages 6366  Notes, example 1.53 (page 65), exercises, answers, quiz 2, answers  
Jan. 28  Regular Expressions Describe Regular Languages  Section 1.3, pages 6669  Notes, exercises, answers, Regular Expressions to NFA  
4  Jan. 31  Regular Languages can be Described by Regular Expressions  Section 1.3, pages 6976  Notes, exercises, answers, quiz 3, answers  
Feb. 2  Nonregular Languages  Section 1.4, pages 7782  Notes, recording, exercises, answers  
Feb. 4  Pumping Lemma Examples  No new readings  Notes, exercises, answers, quiz 4, answers  
5  Feb. 7  More Pumping Lemma Examples  No new readings  What is known about regular langauges, exercises, answers  
Feb. 9  ContextFree Languages  Section 2.1, pages 102107  Notes, slides, exercises, answers  
Feb. 11  Exam 1 moved to Monday  Regular Languages, Chapter 1 
Review
2021 exam,
answers Essay questions, sample answers, exam, sample answers 

6  Feb. 14 

No new readings  
Feb. 16  Ambiguity in Grammars and More Examples  Section 2.1, pages 107108  Notes, exercises, answers  
Feb. 18  Chomsky Normal Form  Section 2.1, pages 108111  Notes, Noam Chomsky and Chomsky hierarchy via Wikipedia, exercises, answers  
7  Feb. 21  President's Day  
Feb. 23  Push Down Automata  Section 2.2, pages 111116  Notes, recording, exercises, answers  
Feb. 25  ContextFree Grammar to a Nondeterministic PDA  Section 2.2, pages 117125  Notes, recursive descent parser from programming languages, recording, exercises, answers  
8  Feb. 28  Nondeterministic PDA to a ContextFree Grammars  Section 2.2, pages 121125  Notes, exercises, answers  
March 2  Pumping Lemma for ContextFree Languages  Section 2.3, pages 125129  Notes , exercises, answers  
March 4  More Pumping Lemma examples for ContextFree Languages  No new readings  Exercises, answers  
9  March 7  
March 9  
March 11  Exam 2  Chapters 1 and 2 
Review
2021 exam,
answers
Essay questions, sample answers, exam, sample answers 

Spring Break, March 1418 

10  March 21  Turing Machines  Section 3.1, pages 165170  Notes, The Imitation Game, Turing's Bombe machine, exercises, answers  
March 23  More Practice Defining Turing Machines  Section 3.1, pages 170175  Exercises, sample answers  
March 25  Variations of Turing Machines  Section 3.2, pages 176  Notes, exercises, answers  
11  March 28  Multitape Turing Machines  Section 3.2, pages 176178  Notes, exercises, answers  
March 30  Nondeterministic Turing Machine  Section 3.2, pages 178180  Notes, recording, exercises, answers  
April 1  Algorithms  Section 3.3, pages 182187  Notes, recording, exercises, answers  
12  April 4  Decidability: Problems Concerning Finite Automaton  Section 4.1, pages 193197  Exercises, sample answers  
April 6  Decidability: Problems Concerning Context Free Languages  Section 4.1, pages 198201  Exercises, sample answers  
April 8  Undecidability  Section 4.2, pages 201202  Notes, exercises, sample answers  
13  April 11  Cantor's Diagonalizaion  Section 4.2, pages 202209  Notes, exercises, sample answers  
April 13  Exam 3  Chapters 1, 2, 3 and 4, pages 193197 
Review,
2021 exam,
answers Essay questions, exam, answers 

April 15  Mini Spring Break  
14  April 18 


April 20  
April 22  Measuring Complexity and the Relationships amoung Complexity Models  Sections 7.1, pages 275286  Notes, exercises, answers  
15  April 25  The Class P  Section 7.2, pages 284291  Notes, exercises, answers  
April 27  Nondeterministic Polynomial Time  Section 7.3, pages 292298  Slides, notes, exercises, answers  
April 29  NPCompleteness and the Cook Levin Theory  Section 7.4, pages 299311  
May 5  Final Exam, Thursday, 3:00pm5:00pm (6:00pm if needed) 
Review,
2021 final,
answers
Essay questions 