CS 420 Theory of Computation • 5 Cr.


This course introduces students to the mathematical foundations of computation and complexity for problem solving, including the concepts of automata theory, the theory of formal languages and grammars, and the notions of algorithm, decidability, complexity, and computability. Students will develop the ability to understand and conduct mathematical proofs for computation and algorithms in order to solve problems efficiently. Prerequisites: MATH 301 and admission to BC CS program, or instructor's permission.


After completing this class, students should be able to:

  • Characterize formal models of computation, such as finite automata, pushdown automata, and Turing machine and regular expressions
  • Design grammars for context-free languages
  • Classify regular and context-free languages based on their properties
  • Design Turing Machines for problems
  • Prove decidability and undecidability of languages
  • Describe class-based resource usage models, including time complexity
  • Apply basic concepts to explain the implications of modern complexity theory approaches to problem-solving