COMP 375 - Theory of Computation

Many complex problems can be solved using a finite state machine approach. This course is a look at various kinds of such theoretical machines and how understanding them can lead to practical solutions to programming problems. Topics include regular languages, context-free languages, finite automata, pushdown automata, nondeterminism and Turing machines. The halting problem and the problem of computability versus undecidability are investigated. The topics are shown to have applications to compiler design; portions of a compiler are implemented in a major project.

Prerequisites
COMP 215 and COMP 121 or COMP 116 and MATH 211 or Permission of Instructor. MATH 211 strongly recommended.

Credits 1

Area
Math and Computer Science