An introduction to the abstract notions encountered in machine computation. Topics include finite automata, regular expressions, and formal languages, with emphasis on regular and context-free grammars. Questions relating to what can and cannot be done by machines are covered by considering various models of computation, including Turing machines, recursive functions, and universal machines.
Prerequisite
C or higher: CSE 160 or CSE 214; CSE 150 or CSE 215; CSE major
Course Outcomes
An ability to define and use abstract models of computation such as finite and push-down automata, and analyze their relative expressive power.
An ability to define, use, and convert between abstract machine models and formal languages.
Understanding of the power and inherent limitations of algorithmic computation.
Textbook
Harry R. Lewis and Christos H. Papadimitriou, Elements of the theory of computation, Prentice Hall. (Second Edition, 1998).
Supplementary Material: Ding-Zhu and Ker-I Ko, Problem Solving in Automata, Languages and Complexity, Wiley.
Major Topics Covered in Course
Strings and languages
Regular languages, regular expressions and finite automata