CS 4810 - Introduction to Theory of Computing

(SMR-AS)

Spring. 3 credits. Student option grading.

Prerequisite: CS 2800 or permission of instructor. Co-meets with CS 5810.

D. Kozen.

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.

Outcome 1: Formally define deterministic and nondeterministic finite automata (DFAs and NFAs, respectively), regular languages, and the notion of acceptance.

Outcome 2: Convert NFAs to DFAs using the subset construction.

Outcome 3: Apply various constructions to produce automata for the intersection, union, and complements of regular sets.