CPSC 4370 - Theory of Computation

Three hours lecture. Three credit hours.

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 CPSC 5370.

Prerequisites: CPSC 2380 or equivalent.