Course Websites

CS 475 - Formal Models of Computation

Last offered Fall 2024

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 or ECE 374.

Related Faculty

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
Formal Models of ComputationC335887PKG3 -    Mahesh Viswanathan
Formal Models of ComputationC335887PKG31530 - 1645 T  1304 Siebel Center for Comp Sci Mahesh Viswanathan
Formal Models of ComputationC435895PKG3 -    Mahesh Viswanathan
Formal Models of ComputationC435895PKG31530 - 1645 T  1304 Siebel Center for Comp Sci Mahesh Viswanathan
Formal Models of ComputationDSO41803ONL4 -    Mahesh Viswanathan
Formal Models of ComputationMC379870PKG3 -    Mahesh Viswanathan
Formal Models of ComputationMC379870PKG31530 - 1645 R  ARR Illini Center Mahesh Viswanathan
Formal Models of ComputationMC479871PKG41530 - 1645 R  ARR Illini Center Mahesh Viswanathan
Formal Models of ComputationMC479871PKG4 -    Mahesh Viswanathan