Theory of Computation - CSC 311

This course explores the limits of computation through the use of different models of computation: finite automata, pushdown automata and Turing machine. Undecidability is explained and the set of undecidable problems is explored using reductions. The related topics of regular expressions, closure properties, pumping lemma, and context-free grammars are covered. An introduction to computational complexity is also given. Prerequisites: CSC 313, MAT 211.