CSC 802
Theory of Computation
3
Course Description
Formal languages; Chomsky hierarchy; formal computation and machine models; finite automata; pushdown automata; Turing machines; Church's Thesis; Recursively enumerable sets.
Course Outline
Formal languages; Chomsky hierarchy; formal computation and machine models; finite automata; pushdown automata; Turing machines; Church's Thesis; Recursively enumerable sets; Diagonal arguments; Reducibility; complexity classes