CS423 Finite Automata & Theory of Computation

Instructor: Weizhen Mao

Textbook: Michael Sipser, Introduction to the Theory of Computation, 3rd edition, Cengage Learning, 2013. Older and international versions are acceptable.

Course Description: The following topics will be covered in this course:

• Automata Theory: Finite automata, pushdown automata, and their corresponding languages and properties.
• Computability Theory: Turing machines, undecidability, proof techniques of reduction and contra- diction.
• Complexity Theory: Complexity classes P and NP, theory of NP-completeness, and polynomial reduction.