Theory of Computation · from zero to fluent

Automata, A to Z

A complete, intuition-first course on automata theory, formal languages, computability and complexity. Every idea comes with the why before the what, a precise definition, worked examples, machines you can run in your browser, and exercises with solutions.

Start with Chapter 1 → Jump to the cheat sheet

What you will be able to do

Design finite automata, regular expressions, grammars, pushdown automata and Turing machines for a given language — and know which model is the right one.
Convert between models: NFA → DFA, regex ↔ automaton, CFG ↔ PDA, any grammar → Chomsky Normal Form, and minimize a DFA.
Prove limits: show a language is not regular (pumping, Myhill–Nerode, closure) or not context-free, and show a problem is undecidable (diagonalization, reductions, Rice's theorem).
Reason about efficiency: P, NP, NP-completeness, polynomial-time reductions, and the space classes.
Recognise the theory in practice: lexers, regex engines, parsers, protocol state machines, static analysis and verification.

The one-sentence story of this whole subject

Give a machine more memory and it can recognise more patterns — finite memory gives regular languages, a stack gives context-free languages, an unbounded tape gives everything computable — and yet even the most powerful machine has problems it can never solve, and many it can solve but not quickly.

How each chapter works

Block	What it is for
Intuition	The mental picture. Read these first; they are what you will remember in five years.
Definition	The precise statement. Learn to read the notation — it is a compact language, not decoration.
Theorem	A guaranteed fact, usually with a proof or proof sketch that shows why it is true.
Pitfall	The mistakes students make most often in exams and interviews.
Interactive	State diagrams you can run: type an input, press Step or Run, watch the active states light up.
Takeaways	The minimum you should be able to say from memory before moving on.

Try one right now. This machine accepts binary numbers that are divisible by 3. Type a binary number and press Run:

A three-state “divisible by 3” machine. State $r_k$ means “the bits read so far form a number with remainder $k$ mod 3”. Reading bit $b$ turns remainder $r$ into $(2r+b) \bmod 3$ — that is all it needs to remember. You will build this yourself in Chapter 3.

The course map

Suggested paths

Taking a university course? Read in order. Chapters 3–10 are typically the first half of the term, 11–15 the second.
Preparing for an exam in a hurry? Read every Intuition and Takeaways box, then do the exercises in Chapter 17 and return to whatever you get wrong.
A working programmer who wants the CS foundations? Chapters 1, 3, 4, 5, 8, 11, 12, 15 and 16 give the highest return per hour.

Prerequisites

Very few. You should be comfortable with basic programming and with reading simple mathematical notation. Everything else — sets, functions, proof by induction, proof by contradiction, countability — is taught from scratch in Chapter 2.

Your progress is saved

At the end of each chapter you can mark it as understood. Progress is stored only in this browser and shows up in the sidebar and on the cards above.