UMBC CMSC451, Automata Theory & Formal Languages, Fall 2008

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


Last Modified: 22 Jul 2024 11:28:20 EDT by Richard Chang
to Fall 2008 CMSC 451 Homepage