Prerequisites and Learning Outcomes

Get a brief introduction to what you'll learn in this course.

We'll cover the following

Who is this course for?

This course is aimed at software engineers who wish to understand the nature and limits of computation, and computing practitioners who want to know what their software can and can’t do.

Prerequisites

Learning the theory of computation will be easier if you have the basic programming knowledge required for typical introductory programming courses. It is also helpful if you’re familiar with these basic concepts from introductory discrete mathematics:

  • Sets
  • Relations
  • Functions
  • Modular arithmetic
  • The notion of a logarithm
  • First-order predicate logic
  • The structure of simple directed graphs

Learning outcomes

In this course, the key results of the theory of computation are covered, with numerous examples and sometimes even with working Python programs, while at the same time achieving a measure of rigor with a minimum of mathematical formalism. Formal proofs appear infrequently, but constructive arguments abound. While mathematical notation appears as needed, visual representations are frequently used to illustrate concepts. The key concepts covered in this course are:

  • Formal languages and finite state machines.
  • Deterministic and nondeterministic finite automata.
  • Regular expressions and grammars.
  • Properties of regular languages.
  • Context-free languages.
  • Pushdown automata.
  • Context-free grammars.
  • Properties of context-free languages.
  • Turing machines.
  • The landscape of formal languages.
  • Computability.

The emphasis is on the structure, properties, and application of formal languages, along with introductory exposure to computability.

In this course, we’ll use Python 3 since Python is the most readable of programming languages; it is often referred to as “executable pseudocode.” It is in widespread use in many computing domains and is universally available. Python syntax is an effective innovation to teach reductions of one unsolvable problem to another in a compact introductory chapter on computability.