CPSI47003 — (was CPSC 4370) Theory of Computation
Add to Bookmarks 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: CPSI28003