The Mathematical Toolkit
The whole subject is built from a handful of ideas: sets, functions, strings, languages, and four or five proof techniques. Learn them well once and every later chapter becomes easier.
Sets
A set is an unordered collection of distinct objects. We write $\{1, 2, 3\}$; order and repetition do not matter, so $\{3,1,1,2\} = \{1,2,3\}$.
| Notation | Meaning | Example |
|---|---|---|
| $x \in A$ | $x$ is an element of $A$ | $2 \in \{1,2,3\}$ |
| $A \subseteq B$ | every element of $A$ is in $B$ | $\{1\} \subseteq \{1,2\}$ |
| $A \cup B$, $A \cap B$ | union, intersection | $\{1,2\}\cup\{2,3\}=\{1,2,3\}$ |
| $A \setminus B$, $\overline{A}$ | difference, complement (relative to a universe) | $\{1,2,3\}\setminus\{2\}=\{1,3\}$ |
| $\emptyset$ | the empty set | $|\emptyset| = 0$ |
| $A \times B$ | Cartesian product: all ordered pairs $(a,b)$ | $\{0,1\}\times\{a\} = \{(0,a),(1,a)\}$ |
| $\mathcal{P}(A)$ or $2^A$ | power set: the set of all subsets | $\mathcal{P}(\{0,1\}) = \{\emptyset,\{0\},\{1\},\{0,1\}\}$ |
| $\{x \in A : P(x)\}$ | set-builder: elements of $A$ satisfying $P$ | $\{n \in \mathbb{N} : n \text{ even}\}$ |
Two facts you will use repeatedly: if $|A| = n$ then $|\mathcal{P}(A)| = 2^n$ (each element is either in or out — this is exactly why converting an NFA with $n$ states to a DFA can create $2^n$ states), and De Morgan’s laws: $\overline{A \cup B} = \overline{A} \cap \overline{B}$ and $\overline{A \cap B} = \overline{A} \cup \overline{B}$.
Functions and relations
A function $f : A \to B$ assigns to every $a \in A$ exactly one $f(a) \in B$. $A$ is the domain, $B$ the codomain. A function is
- injective (one-to-one) if different inputs give different outputs;
- surjective (onto) if every $b \in B$ is hit by some input;
- bijective if both — a perfect pairing between $A$ and $B$.
A partial function may be undefined on some inputs. This matters: a DFA’s transition function is total, but a Turing machine computes a partial function (it may loop forever on some inputs).
A (binary) relation $R$ on $A$ is a set of pairs, $R \subseteq A \times A$. It is an equivalence relation if it is
- reflexive: $x\,R\,x$;
- symmetric: $x\,R\,y \Rightarrow y\,R\,x$;
- transitive: $x\,R\,y$ and $y\,R\,z \Rightarrow x\,R\,z$.
“Has the same remainder mod 3” is an equivalence relation on numbers: it splits $\mathbb{N}$ into three equivalence classes (remainder 0, 1, 2). For the purpose of “is it divisible by 3 after appending more digits?”, two numbers in the same class are interchangeable. That is exactly what a DFA state is — an equivalence class of input histories. Chapter 7 makes this precise (Myhill–Nerode).
Alphabets and strings
- An alphabet $\Sigma$ is a finite, non-empty set of symbols. Examples: $\{0,1\}$, $\{a,b,c\}$, ASCII.
- A string (or word) over $\Sigma$ is a finite sequence of symbols from $\Sigma$, e.g. $0110$.
- The empty string $\varepsilon$ has length 0. (It is a string, not a symbol, and not the empty set.)
- $|w|$ is the length; $|w|_a$ counts occurrences of symbol $a$ in $w$.
- $\Sigma^k$ is the set of strings of length exactly $k$; $\Sigma^* = \bigcup_{k \ge 0}\Sigma^k$ is the set of all strings (including $\varepsilon$); $\Sigma^+ = \Sigma^* \setminus \{\varepsilon\}$.
Operations on strings:
- Concatenation $xy$: $x$ followed by $y$. It is associative, and $\varepsilon$ is its identity: $\varepsilon w = w \varepsilon = w$. Note $|xy| = |x| + |y|$.
- Powers: $w^0 = \varepsilon$, $w^{k+1} = w^k w$. So $(ab)^3 = ababab$ and $a^3 b^2 = aaabb$.
- Reversal $w^R$: $(abc)^R = cba$. A palindrome satisfies $w = w^R$.
- Prefix, suffix, substring: $x$ is a prefix of $w$ if $w = xy$ for some $y$; suffix if $w = yx$; substring if $w = uxv$.
The shortlex (or canonical) order lists strings by length, then alphabetically within a length: $\varepsilon, 0, 1, 00, 01, 10, 11, 000, \dots$ This order lists every string at some finite position — a fact we will use to show $\Sigma^*$ is countable.
Languages
A language over $\Sigma$ is any set of strings over $\Sigma$, i.e. any subset $L \subseteq \Sigma^*$.
Languages can be finite ($\{ab, ba\}$) or infinite ($\{0^n 1^n : n \ge 0\}$). Since they are sets, we can combine them with all the set operations, plus three operations that come from strings:
| Operation | Definition | Example with $A=\{a, ab\}$, $B=\{b\}$ |
|---|---|---|
| Union $A \cup B$ | strings in either | $\{a, ab, b\}$ |
| Concatenation $AB$ | $\{xy : x \in A, y \in B\}$ | $\{ab, abb\}$ |
| Power $A^k$ | $A^0 = \{\varepsilon\}$, $A^{k+1} = A^k A$ | $A^2 = \{aa, aab, aba, abab\}$ |
| Kleene star $A^*$ | $\bigcup_{k\ge 0} A^k$ — any number of pieces glued | $\{\varepsilon, a, ab, aa, aab, aba, abab, \dots\}$ |
| Complement $\overline{A}$ | $\Sigma^* \setminus A$ | all strings except $a$ and $ab$ |
| Reversal $A^R$ | $\{w^R : w \in A\}$ | $\{a, ba\}$ |
$\varepsilon$ is the empty string. $\emptyset$ is the empty language (no strings at all). $\{\varepsilon\}$ is a language containing exactly one string, the empty one. They behave very differently:
$$L\emptyset = \emptyset L = \emptyset \qquad L\{\varepsilon\} = \{\varepsilon\}L = L \qquad \emptyset^* = \{\varepsilon\}$$
Think of $\emptyset$ as “0” and $\{\varepsilon\}$ as “1” for concatenation, which behaves like multiplication.
Proof techniques
Theory of computation is a proof-based subject. You need exactly five techniques; here is each one with a template and an example.
1. Direct proof and proof by construction
Assume the hypothesis, derive the conclusion step by step. In this subject the most common form is proof by construction: to show “there exists a machine that…”, build it and argue it works. Most of Chapters 3–9 are constructions (product automata, subset construction, CFG-to-PDA…).
2. Proof by contradiction
Assume the statement is false and derive something impossible. Template: “Suppose, for contradiction, that $L$ is regular. Then … which contradicts … . Hence $L$ is not regular.” Every pumping-lemma proof and the Halting Problem proof have this shape.
Suppose $\sqrt 2 = p/q$ in lowest terms. Then $p^2 = 2q^2$, so $p^2$ is even, so $p$ is even, say $p = 2k$. Then $4k^2 = 2q^2$, so $q^2 = 2k^2$ and $q$ is even too — contradicting “lowest terms”.
3. Induction
To prove $P(n)$ for all $n \ge 0$: prove the base case $P(0)$, and the inductive step $P(n) \Rightarrow P(n+1)$. For strings we usually induct on length, and for grammars and regular expressions on structure (structural induction: prove it for the base objects, then show each building rule preserves it).
Balanced strings are built by the rules: $\varepsilon$ is balanced; if $x, y$ are balanced so are $(x)$ and $xy$. Base: $|\varepsilon| = 0$ is even. Step: if $|x|$ and $|y|$ are even, then $|(x)| = |x| + 2$ and $|xy| = |x| + |y|$ are even. Every balanced string is built by these rules, so all have even length.
When designing automata, induction is how you prove correctness: state an invariant such as “after reading $w$, the machine is in state $r_k$ iff $w$ represents a number $\equiv k \pmod 3$”, then prove it by induction on $|w|$.
4. The pigeonhole principle
If more than $k$ objects are placed into $k$ boxes, some box contains at least two objects.
It sounds trivial; it is the engine behind the pumping lemmas. A DFA with $k$ states reading a string of length $\ge k$ passes through $k+1$ states, so some state repeats — there is a loop, and loops can be repeated (“pumped”) as many times as we like.
5. Diagonalization
The most beautiful technique in the subject, invented by Georg Cantor. It proves that a list cannot contain everything by constructing an object that differs from the $i$-th item in the $i$-th position.
Countable and uncountable
A set is countable if it is finite or can be put in bijection with $\mathbb{N} = \{0, 1, 2, \dots\}$ — informally, if its elements can be listed as a sequence $x_0, x_1, x_2, \dots$ in which every element eventually appears.
- $\mathbb{N}$, $\mathbb{Z}$, and even $\mathbb{Q}$ are countable.
- $\Sigma^*$ is countable: list strings in shortlex order.
- The set of all programs (or Turing machines) is countable: each one is described by a finite string.
$\mathcal{P}(\Sigma^*)$, the set of all languages over $\Sigma$, is not countable.
Suppose all languages could be listed: $L_0, L_1, L_2, \dots$. List all strings in shortlex order: $s_0, s_1, s_2, \dots$ Build a table with a 1 in row $i$, column $j$ if $s_j \in L_i$. Now define the “diagonal flip” language
$$D = \{ s_i : s_i \notin L_i \}.$$
$D$ differs from every $L_i$ on the string $s_i$: if $s_i \in L_i$ then $s_i \notin D$, and vice versa. So $D$ is not in the list — contradiction.
Programs are countable; languages are uncountable. So almost every language has no program that decides it. There are simply not enough programs to go around. This counting argument does not tell us which problems are unsolvable — Chapter 12 uses the same diagonal trick to exhibit a concrete one, the Halting Problem.
Reading the notation of this course
Formal definitions in this subject are usually tuples: a list of named components. When you meet
$$M = (Q, \Sigma, \delta, q_0, F),$$
read it as a specification of a data structure: “a machine $M$ consists of a set of states $Q$, an alphabet $\Sigma$, a transition function $\delta$, a start state $q_0$ and a set of accept states $F$.” Every symbol has a type. Checking types (“$\delta$ takes a state and a symbol and returns a state”) is the fastest way to understand a definition.
Exercises
Let $\Sigma = \{a,b\}$. List $\Sigma^2$ and compute $|\Sigma^k|$ in general. easy
$\Sigma^2 = \{aa, ab, ba, bb\}$. In general $|\Sigma^k| = |\Sigma|^k = 2^k$: each of the $k$ positions has 2 independent choices.
Compute $\{a, b\}\{\varepsilon, b\}$, $\{a\}\emptyset$, $\emptyset^*$, and $\{\varepsilon\}^*$. easy
$\{a, ab, b, bb\}$; $\emptyset$ (nothing to pair with); $\{\varepsilon\}$ (zero pieces glued give $\varepsilon$); $\{\varepsilon\}$.
Is $L^*$ ever finite? If so, exactly when? medium
$L^*$ is finite exactly when $L \subseteq \{\varepsilon\}$, i.e. $L = \emptyset$ or $L = \{\varepsilon\}$; in both cases $L^* = \{\varepsilon\}$. If $L$ contains any non-empty string $w$, then $w, ww, www, \dots$ are infinitely many distinct strings in $L^*$.
Prove by induction on $|y|$ that $(xy)^R = y^R x^R$. medium
Define reversal by $\varepsilon^R = \varepsilon$ and $(wa)^R = a\,w^R$ for a symbol $a$. Base $y = \varepsilon$: $(x\varepsilon)^R = x^R = \varepsilon^R x^R$. Step $y = za$: $(xza)^R = a\,(xz)^R = a\,z^R x^R = (za)^R x^R = y^R x^R$, using the induction hypothesis for $z$.
Show that the relation “$x \sim y$ iff $|x|$ and $|y|$ have the same parity” on $\Sigma^*$ is an equivalence relation. How many classes does it have? easy
Reflexive, symmetric and transitive follow immediately from the corresponding properties of equality of parities. There are two classes: even-length strings and odd-length strings. (A two-state DFA tracks exactly this.)
Show that the set of infinite binary sequences is uncountable, using diagonalization. medium
Suppose $b_0, b_1, \dots$ lists them all, and write $b_i[j]$ for the $j$-th bit of $b_i$. Define $d[j] = 1 - b_j[j]$. Then $d$ differs from each $b_i$ at position $i$, so it is not in the list. (Note: this is the same argument as for languages, because a language over $\Sigma$ is exactly an infinite bit-sequence indexed by $s_0, s_1, \dots$ — its characteristic sequence.)
Seven DFAs each have at most 3 states. Among 22 different input strings run on one 3-state DFA, how many are guaranteed to end in the same state? easy
By the generalized pigeonhole principle, at least $\lceil 22/3 \rceil = 8$ strings end in the same state. (The seven DFAs were a distraction.)
- Strings are finite sequences over a finite alphabet; $\Sigma^*$ is all of them; a language is any subset of $\Sigma^*$.
- Know concatenation, star and complement cold, and never confuse $\varepsilon$, $\emptyset$ and $\{\varepsilon\}$.
- Five proof tools: construction, contradiction, induction (incl. structural), pigeonhole, diagonalization.
- Programs are countable, languages are not — so most languages are undecidable.