Theory of Computation

Automata, formal languages, computability and complexity, with proofs: alphabets, strings and languages, countability and diagonalization; deterministic and nondeterministic finite automata and the subset construction; regular expressions, Kleene's theorem, closure and decision properties; the pumping lemma, the Myhill–Nerode theorem and DFA minimization; context-free grammars, ambiguity, Chomsky normal form and the CYK algorithm; pushdown automata, determinism and the context-free pumping lemma; Turing machines, their variants, universal machines, the Church–Turing thesis and busy beavers; decidable problems, the undecidability of acceptance and halting, and recognizability; mapping reductions, Rice's theorem, the Post Correspondence Problem, undecidable questions about grammars and Kolmogorov complexity; P, NP, the Cook–Levin theorem and NP-complete reductions; space complexity, Savitch's theorem, PSPACE-completeness, L, NL and the hierarchy theorems; and a capstone on randomized, approximation, parameterized and quantum complexity, cryptography and SAT solvers.

CMPUT-474 Year 4 3 credits 12 lessons · 6 h 32 min

Offered by HSM University · Computing Science

This is the American version of this course. See the Canadian version.

What you'll learn

Model computational problems as languages over an alphabet, and use construction, induction, contradiction, diagonalization and reduction in proofs about them.
Design deterministic and nondeterministic finite automata, convert between them with the subset construction, and explain the exponential worst case.
Convert between regular expressions and finite automata using Kleene's theorem, and apply closure and decision properties of regular languages.
Prove that languages are not regular with the pumping lemma, closure properties and the Myhill–Nerode theorem, and minimize DFAs.
Write and analyze context-free grammars, recognize and remove ambiguity where possible, convert grammars to Chomsky normal form and apply the CYK algorithm.
Design pushdown automata, explain their equivalence with grammars and the role of determinism, and prove languages not context-free.
Define Turing machines and their variants, explain why the variants are equivalent, and state the Church–Turing thesis and its limits.
Prove decidability results for automata and grammars, prove the acceptance and halting problems undecidable, and relate recognizability and co-recognizability.
Use mapping reductions and Rice's theorem to show problems undecidable, including the Post Correspondence Problem and questions about grammars.
Define P, NP and NP-completeness, explain the Cook–Levin theorem, and construct polynomial-time reductions between NP-complete problems.
Explain space complexity, Savitch's theorem, PSPACE-completeness, L and NL, and use the hierarchy theorems to separate complexity classes.
Describe randomized, approximation, parameterized and quantum complexity, the complexity assumptions behind cryptography, and why SAT solvers succeed in practice.

Course content

12 lessons · 6 h 32 min total · final exam

1 Languages, proofs and models of computation 33 min · quiz
2 Finite automata and nondeterminism 33 min · quiz
3 Regular expressions and closure properties 33 min · quiz
4 Limits of regular languages: pumping and Myhill–Nerode 31 min · quiz
5 Context-free grammars and normal forms 32 min · quiz
6 Pushdown automata and limits of context-free languages 31 min · quiz
7 Turing machines and the Church–Turing thesis 34 min · quiz
8 Decidability and the halting problem 31 min · quiz
9 Reductions, Rice's theorem and undecidable problems 33 min · quiz
10 Time complexity: P, NP and NP-completeness 34 min · quiz
11 Space complexity and the hierarchy theorems 32 min · quiz
12 Capstone: randomness, approximation, quantum computing and complexity in practice 35 min · quiz
E Final exam 20 questions

Requirements

Recommended background. You can start any course at any time.

Description

Part of the Science stream, typically taken in year 4.