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

Distribution Requirements: MM - Mathematical Modeling and Problem Solving

Typical Periods Offered: Spring; Fall

Semesters Offered this Academic Year: Fall; Spring

Notes: