CS 4810

Introduction to Theory of Computing

Course Description

Course information provided by the 2024-2025 Catalog. Courses of Study 2024-2025 is scheduled to publish mid-June.

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.

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

Last 4 Terms Offered 2025SP, 2022SP, 2019FA, 2018FA

Outcomes

• 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.

Distribution Category (SMR-AS)

When Offered Spring.

View Enrollment Information