CSCI 341 : Theory of Computation

Introduction to the classical theory of computer science. A study of the formal relationships between machines, languages and grammars, we will cover regular, context-free, context-sensitive, recursive and recursive enumerable languages. Sequential machines and their applications to devices, processes, and programming. Models of computation: finite state automata, push down automata, Turing machines. The role of non-determinism