CMPS 3250/6250 Theory of Computation

CMPS 3250/6250 Theory of Computation
Theory of Computation
This course is an introduction to the theory of computation. It begins with regular languages and their representation as finite state automata, and continues with context free languages and pushdown automata. Turing machines and the Church-Turing Thesis are also considered, as well as decidability and reducibility. The basic notions of complexity theory area also covered, including P and NP for time complexity, as well as basic results about space complexity.
Pre-requistites: CMPS/MATH 2170 or equivalent.
credit hours: 3