UMBC CMSC451/651, Automata Theory & Formal Languages, Fall 2011

Syllabus


We will follow the textbook Introduction to the Theory of Computation (second edition) by Michael Sipser. The following schedule outlines the material to be covered during the semester and specifies the corresponding sections in the textbook.


Date Topic Quizzes Reading Homework
Assign Due
Thu 09/01 Introduction   0.1–0.4    
Tue 09/06 Deterministic Finite Automata (DFA)   1.1 HW1  
Thu 09/08 Nondeterministic Finite Automata (NFA)   1.2    
Tue 09/13 Equivalence of DFAs & NFAs     HW2 HW1
Thu 09/15 Regular Expressions   1.3    
Tue 09/20 Equivalence of Regular Expressions     HW3 HW2
Thu 09/22 Regular Language Pumping Lemma   1.4    
Tue 09/27 Context-free Grammars (CFG)   2.1 HW4 HW3
Thu 09/29 Context-free Grammars (CFG) Quiz 1      
Tue 10/04 Chomsky Normal Form     HW5 HW4
Thu 10/06 Pushdown Automata (PDA)   2.2    
Tue 10/11 PDAs for CFGs     HW6 HW5
Thu 10/13 CFGs for PDAs Quiz 2      
Tue 10/18 Context-Free Pumping Lemma   2.3 HW7 HW6
Thu 10/20 Turing Machines   3.1-3.2    
Tue 10/25 Decidable Properties   4.1 HW8 HW7
Thu 10/27 The Halting Problem Quiz 3 4.2    
Tue 11/01 Undecidability   5.1–5.2 HW9 HW8
Thu 11/03 Reductions   5.3    
Tue 11/08 Reductions     HW10 HW9
Thu 11/10 Kleene Hierarchy Quiz 4      
Tue 11/15 Time & Space Hierarchy   7.1 HW11 HW10
Thu 11/17 P vs NP   7.2–7.3    
Tue 11/22 NP-Completeness   7.4   HW11
Thu 11/24 Thanksgiving Break
Tue 11/29 NP-Completeness   7.5 HW12  
Thu 12/01 Recursion Theorem   6.1    
Tue 12/06 Kolmogorov Complexity Quiz 5 6.4 HW13 HW12
Thu 12/08 Kolmogorov Complexity & HeapSort        
Tue 12/13 Review       HW13
Tue 12/20 Final Exam 10:30am – 12:30pm


Last Modified: 22 Jul 2024 11:29:16 EDT by Richard Chang
to Fall 2011 CMSC 451/651 Homepage