Academic Calendar 2020/2021 - Theory of Computation

COSC 3206  Theory of Computation

Prerequisites:

COSC 2006

Hours:

Three hours of lecture per week for one term.

Credits:

3

Description:

The course introduces the theory of computability, automata theory and formal languages. The topics include automata and regular, context-free and context-sensitive languages, general theory of computability including Turing machines, recursive functions, decidability and undecidability. Approaches to formal program semantics are presented and analyzed, leading to an introduction to formal program verification.