skip to main content

CS 475 - Formal Models of Computation

Fall 2020

Official Description

Finite automata and regular languages; pushdown automata and context-free languages; Turing machines and recursively enumerable sets; linear-bounded automata and context-sensitive languages; computability and the halting problem; undecidable problems; recursive functions; Chomsky hierarchy; computational complexity. Course Information: Same as MATH 475. 3 undergraduate hours. 3 or 4 graduate hours. Prerequisite: CS 374.

Course Director


Primary Textbook: Theory of Computation by Dexter Kozen

For Background and Additional Topics: Automata and Computability by Dexter Kozen

Learning Goals

[1] Recognize regular and non-regular languages (1), (6)

[2] Prove recursive/recursive enumerability of sets (1), (6)

[3] Prove problems to be undecidable/non-recursively enumerable through reductions (6)

[4] Understand the relationship between complexity classes (6)

[5] Prove that a problem belongs to a certain complexity class (1)

[6] Prove that a problem is the hardest in a complexity class through reductions (6)

[7] Understand the power of nondeterminism in a computational setting (6)

[8] Understand the power of randomization in a computational setting (6)

Topic List

Automata Theory:

  • Deterministic/nondeterminstic finite automata
  • Regular languages
  • 2-way automata, alternation

Recursion Theory:

  • Turing machine and its variants
  • Recursive enumerability and decidability
  • Reductions
  • Arithmetic Hierarchy

Complexity Theory

  • Definitions of time and space bounded complexity, and classical complexity classes
  • Relationship between complexity classes
  • Alternation and randomization
  • Interactive proofs

Last updated

2/8/2019by Mahesh Viswanathan