Easier to read with cream paper, a tint, more contrast or larger text? Choose your colours and text, once, for every page.

Free module

Theory of computation

Learn the theory of computation hands on: finite automata, regular expressions, grammars, Turing machines and what no program can decide.

5 lessons280 min lessonCore computer science

The lessons

Each lesson is free to read in full. Create a free account to run its commands in a live lab and to sit its quizzes and tasks.

  1. 1 · Virtual machine lab

    Finite automata (finite state machines)

    I can trace a finite automaton and say which strings it accepts.

    Read the lesson

  2. 2 · Virtual machine lab

    Regular expressions with grep

    I can write a regular expression and test it with grep.

    Read the lesson

  3. 3 · Virtual machine lab

    Context-free grammars and derivations

    I can use a grammar to decide whether a string is valid.

    Read the lesson

  4. 4 · Virtual machine lab

    How a Turing machine works

    I can trace a Turing machine on a tape.

    Read the lesson

  5. 5 · Virtual machine lab

    The halting problem and limits of computing

    I can explain why no program can decide every question, and what too slow means.

    Read the lesson

Worked in a real lab

Every lesson of this module is worked in a lab started for you alone. The labs it uses:

Teaching a class? Set this module for your students with a teacher guide, marked assignments and a lab for every student.