Computer Science 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.