This course offers an introduction to the theory of computation. Topics include languages, regular expressions, finite automata, grammars, pushdown automata, and Turing machines. The first part of the course covers the Chomsky hierarchy of languages and their associated computational models. The second part of the course focuses on decidability issues and unsolvable problems. The final part of the course investigates complexity theory.

Units: 1

Max Enrollment: 24

Prerequisites: CS 230 (or CS 230P or CS 230X) and MATH 225, or permission of the instructor.

Instructor: Staff

Typical Periods Offered: Spring; Fall

Notes: