COMP 381 - THEORY OF COMPUTATION

Hours: 3
Models of computation based on machine models and formal grammars: finite automata; regular languages, pushdown automata, context free languages, Turing machines, recursive languages, and recursively enumerable languages; the Chomsky hierarchy of languages; the Church-Turing thesis; introduction to the halting problem and computability issues.
Prerequisites: COMP 205 and MATH 165.