Prerequisites: (CS 241 or MATH 226) and CS 280 with a grade C or better. This course provides an introduction to automata theory, computability theory, and complexity theory. Theoretical models such as finite-state machines, push-down stack machines, and Turing machines are developed and related to issues in programming language theory. Also, the course covers undecidability and complexity classes P, NP, and NPC.