CS 311 / MATH 352

Automata and Complexity Theory

This is an introductory course in the theory of computation. The main goals of this course are to introduce students to theoretical computer science and to give them a better understanding of the computational process. Students are introduced to automata theory, formal languages, and recursive functions in the context of practical applications. In automata theory they learn about finite automata, deterministic automata, non-deterministic automata, minimisation of finite automata, and push-down automata. In formal languages, they learn about regular grammars, regular expressions, context-free grammars, Turing machines and phrase-structure languages.