CPSC 3630

Computation as strings and languages. Regular languages, finite state automata and their equivalence. Formal Grammars. Context-free languages, push-down automata and their equivalence. Recursive languages and recursively enumerable languages. Turing machines and effective computability. Church's thesis. The Chomsky hierarchy. Prerequisite(s): One of Computer Science 1620 or admission to the Post-Diploma B.Sc. in Computer Science AND Mathematics 2000