Practice

Chapter 1 exercises

Theory of Computation practice problems

Practice building DFAs, NFAs and regular expressions, the way Chapter 1 of Sipser teaches them. Every answer is checked exactly: if it is wrong, you get the shortest string your answer gets wrong, so you can see where your machine goes off track.

How it works

  1. Pick an exercise from the menu in the panel.
  2. Draw your machine on the canvas, or type a regular expression when the exercise asks for one.
  3. Press Check answer. If it is wrong, step through the counterexample in the Test tab.
  4. Stuck? Open a Hint, or look at a solution and press Undo to get your own work back.

What is checked

  • The language: your answer must accept exactly the right strings, of every length.
  • The rules: “must be a DFA”, “at most 4 states”, or “as few states as possible”.
  • The alphabet: only symbols from Σ.

Your drawings and progress stay in this browser.