Description

A survey of the mathematical foundations of Computer Science. Finite automata and regular languages. Stack Acceptors and Context-Free Languages. Turing Machines, recursive and recursively enumerable sets. Decidability. Complexity. This course involves no computer programming. This course is for CS graduate students needing it to fulfill prerequisite requirements. It is not available to CS undergraduates without specific permission from the Undergraduate Coordinator.