Theory of Computation

Undergraduate

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), BCB, CAST, CNET, GAMP and NEUR Neurocomputing stream majors. Prerequisite(s): MATH 1P67 (minimum 60 percent) and three and one-half COSC credits Cross-Listing(s): COSC 4P61 Course Notes: MATH students who do not meet the prerequisite may take this course with permission of the Department of Mathematics and Statistics. This course may be offered in multiple modes of delivery. The method of delivery will be listed on the academic timetable, in the applicable term.