CS 4810

Introduction to Theory of Computing

Course Description

Course information provided by the Courses of Study 2024-2025.

An introduction to the classical theory of computing: automata theory, formal languages, and effective computability. Topics include finite-state machines, regular languages, regular expressions, grammars, context-free languages, pushdown automata, Turing machines, recursive and recursively enumerable sets, diagonalization, reductions, undecidability, Gödel's incompleteness theorem. A complete list of topics can be found on the schedule page (subject to change). As time permits, we will explore some more modern advances such as coalgebraic methods, abstract interpretation, and concurrency.

When Offered Spring.

Prerequisites/Corequisites Prerequisite: CS 2800 or permission of instructor.

Distribution Category (SMR-AS)

• Formally define deterministic and nondeterministic finite automata (DFAs and NFAs, respectively), regular languages, and the notion of acceptance.
• Convert NFAs to DFAs using the subset construction.
• Apply various constructions to produce automata for the intersection, union, and complements of regular sets.

View Enrollment Information