CS 21: Decidability and Tractability (Winter 2010)
Instructor: Chris
Umans
TAs:
Ombudsperson: Martin Michelsen
Office: Annenberg 311
Times: MWF 1:00-1:55 in Annenberg 105
Office hours:
- Tuesday 3-4 in Annenberg 311 (Chris)
- Tuesday 4-5 in Annenberg 106 (Carol)
- Tuesday 7-8 in Annenberg 106 (Karthik)
- Tuesday 8-9 in Annenberg 106 (Patrick)
Announcements:
- CLARIFICATION for MIDTERM #1(b): the definition of language
L_2 should read "...for some integers x, y, z..." rather than "...for
integers x,y,z...". In other words, a^6 is in the language, and so is
a^(6+9), etc... [I would interpret the original version to
implicitly mean "for
some" but I'm clarifying just in case].
- The midterm has been posted. It is due Wednesday February 10 at the beginning of class.
- Solutions to Problem Set 3 have been posted. If you are turning it in late, please do not consult these until after you have turned it in.
Handouts:
Lecture Slides:
- Lecture 1: Introduction, Languages, Finite Automata (ppt, pdf) [p. 1-43]
- Lecture 2: Nondeterministic Finite Automata, closure under regular operations, NFAs and FAs (ppt, pdf) [p. 44-63]
- Lecture 3: NFA and FA equivalence, regular expressions, regular expression and FA equivalence (ppt, pdf) [p. 64-77]
- Lecture 4: the pumping lemma and non-regular languages, pushdown automata (ppt, pdf) [p. 77-82, 109-114]
- Lecture 5: Context-Free Grammars, parse trees, ambiguity, Chomsky Normal Form (ppt, pdf) [p. 99-109]
- Lecture 6: NPDA and CFG equivalence, Pumping Lemma
for CFLs and non-context-free languages (ppt,
pdf) [p. 115-127]
- Lecture 7: proof of Pumping Lemma
for CFLs, deterministic CFLs, closure of DFLs under complement (ppt,
pdf)
- Lecture 8: deciding CFLs (CKY algorithm), Turing Machines and variants (ppt,
pdf) [p. 137-141]
- Lecture 9: Turing Machines, multi-tape TMs, nondeterministic TMs, Church-Turing thesis, recursive enumerability (ppt,
pdf) [p. 142-159]
- Lecture 10: undecidable (and non-RE) languages, the Halting Problem, co-RE, a natural non-RE language (ppt,
pdf) [p. 173-182]
- Lecture 11: reductions, many-one reductions, undecidable languages (ppt,
pdf) [p. 187-191, 206-210]
- Lecture 12: decidable and undecidable problems, reductions based on computation histories (ppt,
pdf) [p. 192-198]
- Lecture 13: Rice's Theorem, Post Correspondence Problem, a natural non-RE and non-co-RE language (ppt,
pdf) [p. 199-205, 210]
- Lecture 14: Recursion Theorem, Godel Incompleteness Theorem (ppt,
pdf) [p. 217-224]
- Lecture 15: proof of Godel Incompletness Theorem (ppt,
pdf)
Problem Sets and Exams: