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 218 and COMP 121 or permission of instructor

Credits 1

Area
Math and Computer Science