Course Information | |
Course Code |
MATH 4P61 (also offered as |
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 |
Prerequisite(s) | |
Notes | MATH students may take this course with permission of Department. |