Abstract basis of computing machines and languages; introduction to formal languages, finite automata, grammars, turing machines, and complexity theory. Prerequisites: CS 143 and CS 150M.