The Big Picture
Before any definitions: what is this subject actually about, why did people invent it, and why is it still one of the most useful things a computer scientist can know?
The question behind everything
Every program you have ever written takes some input, does something, and produces an output. Strip away the details — the language, the hardware, the libraries — and ask the most basic question possible:
What can a machine compute at all — and what does it need in order to do it?
Automata theory answers this by studying idealised machines: mathematical models so simple that we can prove things about them, yet powerful enough to capture real computation. Instead of asking “what does this particular laptop do?” we ask “what can any machine with this kind of memory do?”
Imagine checking whether a long string of brackets like (()(())) is balanced, reading it one character at a time.
- If you are only allowed to remember a fixed number of things (say, a single digit), you will fail on deeply nested input — you cannot remember how deep you are once it exceeds your memory.
- If you have a stack of plates — push on
(, pop on)— the problem becomes trivial. - If you have an unbounded notebook you can read and rewrite anywhere, you can do anything any computer can do.
Those three kinds of memory are exactly the three great machine models of this course: finite automata, pushdown automata, and Turing machines.
A first machine: the turnstile
A subway turnstile is locked until you insert a coin (c); then it is unlocked until somebody pushes (p) through it, which locks it again. That is all it needs to remember — one bit: locked or unlocked.
cpcpp, ccc, or the empty input.Notice what the machine does not do: it does not count coins, store a history, or look ahead. It reads one symbol, updates its state, and forgets the symbol. This extreme simplicity is what makes it analyzable — and, surprisingly, it is enough for a huge range of real problems: lexical analysis in compilers, network protocols, UI flows, digital circuits, text search.
Problems are languages
To study “what can be computed” mathematically, we need one uniform shape for every problem. The trick that makes the whole subject work:
Encode every input as a string of symbols. A yes/no problem is then just the set of strings whose answer is “yes”. That set is called a language, and “solving the problem” means deciding, for any string, whether it belongs to the language.
| Problem | Language (the “yes” instances) |
|---|---|
| Is this binary number divisible by 3? | $\{0, 11, 110, 1001, 1100, \dots\}$ |
| Are these brackets balanced? | $\{\varepsilon, (), (()), ()(), \dots\}$ |
| Is this number prime? | $\{10, 11, 101, 111, 1011, \dots\}$ (primes in binary) |
| Does this program compile? | the set of syntactically valid source files |
| Does this program halt on this input? | $\{\langle P, x\rangle : P \text{ halts on } x\}$ |
This is not a loss of generality. A function problem (“compute f(x)”) can be turned into decision problems (“is the i-th bit of f(x) equal to 1?”), and optimization problems into threshold questions (“is there a route shorter than k?”). Languages are the universal currency of the theory.
The ladder of machines
Each model adds a little more memory and gains a little more power. The languages each model can recognise form a strict hierarchy of nested classes:
| Machine | Memory | Recognises | Typical example it can do | …but cannot do |
|---|---|---|---|---|
| Finite automaton (DFA/NFA) | finitely many states | Regular languages | “contains ab”, numbers divisible by 3 | $a^n b^n$ (needs to count) |
| Pushdown automaton (PDA) | states + one stack | Context-free languages | $a^n b^n$, balanced brackets, arithmetic expressions | $a^n b^n c^n$ (two counts) |
| Linear-bounded automaton | tape as long as the input | Context-sensitive languages | $a^n b^n c^n$, $\{ww\}$ | some decidable problems |
| Turing machine (TM) | unbounded read/write tape | Recognizable / decidable languages | anything an algorithm can do | the Halting Problem |
Three big questions, three parts of the subject
- Automata & formal languages (Chapters 3–10, 14): What can simple machines do? How do we design them, convert between them, and prove what they cannot do?
- Computability (Chapters 11–13): What can be computed at all? Here we meet the Turing machine and discover — with a proof — that some well-defined problems have no algorithm whatsoever.
- Complexity (Chapter 15): What can be computed efficiently? P, NP, NP-completeness, and the most famous open problem in computer science.
It is easy to show a problem can be solved: write the program. Showing that a problem cannot be solved by any machine of a certain kind — no matter how clever the programmer — requires understanding the model so deeply that you can reason about all possible machines at once. That is what this subject trains, and it is a superpower: it tells you when to stop looking for a perfect solution and switch to an approximation.
Why this matters in practice
- Regex and lexers. Every regular-expression engine and every compiler front end is a finite automaton in disguise. Knowing the theory explains why some regexes are slow (and how to make them fast), and why regexes famously cannot parse HTML.
- Parsers. Programming-language syntax is described by context-free grammars; parser generators (yacc, ANTLR, tree-sitter) turn them into pushdown automata.
- State machines in software. Protocols (TCP), game AI, UI workflows, payment flows, embedded controllers — all modelled as finite-state machines, often with formal verification.
- Limits of tools. No compiler can detect all infinite loops; no antivirus can detect all viruses; no linter can find all bugs. These are theorems (Halting Problem, Rice’s Theorem), not engineering failures.
- Algorithms and security. NP-completeness tells you when a problem is probably intractable; much of modern cryptography assumes certain problems are hard.
A short history
| Year | Milestone |
|---|---|
| 1936 | Alan Turing defines the Turing machine and proves the Halting Problem undecidable; Alonzo Church independently does the same with the λ-calculus. |
| 1943 | McCulloch & Pitts model neurons as finite-state devices — the first finite automata. |
| 1951–56 | Kleene invents regular expressions and proves they match finite automata exactly. |
| 1956–59 | Chomsky classifies grammars into a hierarchy; Rabin & Scott introduce nondeterministic finite automata (Turing Award). |
| 1960s | Context-free grammars (BNF) describe ALGOL; parsing theory (LL, LR) is born; Hartmanis & Stearns found complexity theory. |
| 1971–72 | Cook and Levin prove SAT is NP-complete; Karp shows 21 classic problems are NP-complete. |
| Today | P vs NP remains open — one of the Millennium Prize Problems. |
How to study this subject
- Draw the machine. For every language, sketch states and arrows before writing anything formal. Then run a few strings through it by hand (or in the simulators here).
- Ask “what must be remembered?” This one question designs most automata, and its negative (“infinitely many things must be remembered”) drives most impossibility proofs.
- Treat proofs as games. Pumping lemmas, diagonalization, reductions — each is a game with a precise sequence of moves. Learn the moves.
- Do the exercises before looking at solutions. The struggle is where the understanding is built.
Exercises
Express “Is a given graph connected?” as a language. What is the alphabet, and what are the strings? easy
Pick an encoding, e.g. the number of vertices in binary followed by a list of edges (i,j), over the alphabet $\{0,1,(,),\#,\text{comma}\}$. The language is the set of strings that are valid encodings of connected graphs. Invalid encodings are simply not in the language. The precise encoding does not matter for any question in this course, as long as it is reasonable (we revisit this in Chapter 11).
The turnstile above accepts exactly the event sequences after which it is open. Describe that language in plain words. easy
Sequences of c and p whose last symbol is c. A coin always opens the turnstile; a push always locks it — so only the final event matters. (This is a good example of a state remembering a summary of the past, not the past itself.)
Without any formal tools, argue why a machine with only finitely many states cannot check that a string has the form $a^n b^n$ (some number of a’s followed by the same number of b’s). medium
After reading $a^n$ the machine must “know” $n$ to check the b’s that follow. If it has only $k$ states, then among the $k+1$ strings $a^0, a^1, \dots, a^k$ two of them, say $a^i$ and $a^j$ with $i \ne j$, leave it in the same state (pigeonhole principle). From then on it behaves identically, so it gives the same answer on $a^i b^i$ and $a^j b^i$ — but one is in the language and the other is not. This argument is the heart of Chapters 6 and 7.
Name a task from your own programming experience that is naturally a finite-state machine, and one that clearly needs more memory. easy
Finite-state: a traffic light controller, a login flow (logged out → entering password → logged in → locked after 3 failures), parsing a number literal like -12.5e3. Needs more: matching nested HTML tags or JSON brackets (needs a stack), evaluating arbitrary arithmetic expressions, sorting a list (needs memory proportional to the input).
- Automata theory studies idealised machines to learn what is computable with a given kind of memory.
- Decision problems are modelled as languages: sets of strings whose answer is “yes”.
- Finite memory → regular languages; a stack → context-free; an unbounded tape → everything computable.
- Even Turing machines have limits (undecidability), and even decidable problems may be infeasible (complexity).