UMBC CMSC451h, Automata Theory & Formal Languages, Spring 2010

Course Syllabus

Updated March 23, 2010

This syllabus has been updated. The previous syllabus and the original syllabus are still available.


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 01/28 Introduction 0.1–0.4
Tue 02/02 Deterministic Finite Automata (DFA) 1.1 HW1
Thu 02/04 Nondeterministic Finite Automata (NFA) 1.2
Tue 02/09 Campus Closed (snow)
Thu 02/11 Campus Closed (snow)
Tue 02/16 Equivalence of DFAs & NFAs HW2 HW1
Thu 02/18 Regular Expressions 1.3
Tue 02/23 Regular Language Pumping Lemma 1.4 HW3 HW2
Thu 02/25 Context-free Grammars (CFG) Quiz 1 2.1
Tue 03/02 Chomsky Normal Form HW4 HW3
Thu 03/04 Pushdown Automata (PDA) 2.2
Tue 03/09 CFGs for PDAs HW5 HW4
Thu 03/11 PDAs for CFGs Quiz 2
Tue 03/16 Spring Break
Thu 03/18 Spring Break
Tue 03/23 Context-Free Pumping Lemma 2.3 HW6 HW5
Thu 03/25 Turing Machines 3.1
Tue 03/30 Turing Machines 3.2 HW7 HW6
Thu 04/01 Regular Language Decision Properties Quiz 3 4.1
Tue 04/06 Context-free Decision Properties HW8 HW7
Thu 04/08 The Halting Problem 4.2
Tue 04/13 Undecidability 5.1 HW9 HW8
Thu 04/15 Undecidability Quiz 4 5.2
Tue 04/20 Reductions 5.3 HW10 HW9
Thu 04/22 P vs NP 7.1 – 7.3
Tue 04/27 NP-completeness 7.4 HW11 HW10
Thu 04/29 NP-completeness Quiz 5 7.5
Tue 05/04 Advanced Topic TBA HW12 HW11
Thu 05/06 Advanced Topic TBA
Tue 05/11 Advanced Topic TBA HW12
Thu 05/13 Advanced Topic TBA
Tue 05/18 Final Exam 10:30am – 12:30pm


Last Modified: 22 Jul 2024 11:29:19 EDT by Richard Chang
to Spring 2010 CMSC 451h Homepage