CPSI 47003 - (was CPSC 4370) Theory of Computation

Three hours lecture. Three credit hours.

Was CPSC 4370. Introduction to and overview of models of computation: finite-state automata, pushdown automata, and Turing machines. Study of grammars and their relation to automata. Chomsky hierarchy and relations between classes of formal languages. Discussion of computational complexity including NP-completeness, limits of computability as well as unsolvability, and the Church-Turing thesis. Dual listed in the Graduate Catalog as CPSI 57003 (was CPSC 5370).

Prerequisites: CPSI 28003 or equivalent.