Formal models of computation such as finite state automata, recursive functions, formal grammars and Turing machines will be studied. These models will be used to provide a mathematical basis for the study of computability. Applications to compiler design and computational undecidability will also be covered. Evaluation will be based primarily on problem assignments and exams. Prerequisites: Computer Science 256 or both a 300-level mathematics course and permission of the instructor.