CMPUT 474 - Formal Languages, Automata and Computability

Overview

An introduction to the theory of computation; topics include: formal languages, automata, Turing machines, the halting problem, computability, and complexity.

Objectives

• Understand the theoretical capabilities and limitations of models of computation
• Be able to prove the undecidability or complexity of problems

Course Work

• Assignments
• Midterm Exam
• Final Exam