Course Information
Course Code COSC 4P61
(also offered as MATH 4P61)
Course Title Theory of Computation
Description Regular languages and finite state machines: deterministic and non-deterministic machines, Kleene's theorem, the pumping lemma, Myhill-Nerode Theorem and decidable questions. Context-free languages: generation by context-free grammars and acceptance by pushdown automata, pumping lemma, closure properties, decidability. Turing machines: recursively enumerable languages, universal Turing machines, halting problem and other undecidable questions.
Course Format Lectures, 3 hours per week.
Restrictions open to COSC (single or combined) majors.
Prerequisite(s) MATH 1P67.
Notes MATH students may take this course with permission of the Mathematics Department.