CSE303

Course CSE303
Title Introduction to the Theory of Computation
Credits 3
Course Coordinator

Jing Chen

Description

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 214 and 215 and 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
  • Context-free grammars, parsing, pushdown automata
  • Turing machines, unrestricted grammars, Church-Turing thesis
  • Introduction to recursion theory, universal Turing machine, halting problem, undecidability

Laboratory Projects

No large scale projects are required.

Course Webpage

CSE303