**Units: **

4

An introduction to the mathematical theory of computability. Formal languages. Finite automata and regular expression. Push-down automata and context-free languages. Computable or recursive functions: Turing machines, the halting problem. Undecidability.

**Course Objectives: **

This course gives a precise definition of the notion of an algorithm as well as developing a theory of automata and formal languages. The course stresses the understanding of the basic concepts and constructions.

**Prerequisites: **

CSE 12, CSE 15L, CSE 21 or Math 154 or Math 184A or Math 100A or Math 103A; restricted to SO, JR, SR standing. Graduate students will be allowed as space permits. Please see **Prerequisites page**.

**Other Restrictions: **

Credit not offered for both Math 166 and CSE 105. Equivalent to Math 166.

**Offered: **

Three sections per year.