CS 4810

Last Updated

  • Schedule of Classes - September 22, 2025 1:06PM EDT

CS 4810
Introduction to Theory of Computing

Course information provided by the 2025-2026 Catalog.

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, Godel'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 CS 2800 or permission of instructor.

Distribution Requirements (SMR-AS)

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.

View Enrollment Information

Syllabi: none

  •   Regular Academic Session. 

  • 3 Credits Stdnt Opt

  •  8916 CS 4810   LEC 001

  •  
    • TR
    • Jan 20 - May 5, 2026

    • Kozen, D

  • Instruction Mode: In Person

    For Bowers Computer and Information Science (CIS) Course Enrollment Help, please see: https://tdx.cornell.edu/TDClient/193/Portal/Home/