CMPS 440(G) - Theory of Computation

3 Credit(s). 0 Hour(s) Lab. 3 Hour(s) Lecture.

Abstract basis of machines and programming; automata, context free grammars, and Turing machines; equivalence and non-equivalence of classes of devices; Chomsky hierarchy; incomputability; computational complexity.

Prereq: CMPS 341 with a grade of “C”.