[Intermediate → Advanced] · Worked answers to note 09.
Part A — Automata and regular languages
1. Three DFAs
(a) Even number of 0s. Two states: (accepting), . 0 flips; 1 self-loops. The state is the parity — that’s the design principle: a DFA’s state set is exactly the information you must remember.
(b) Divisible by 3. Three states = the remainder mod 3 so far. Reading a bit doubles the value and adds , so . Start and accept at .
This is the one worth doing. It shows a finite machine handling arbitrarily large numbers — because it never stores the number, only the residue. Bounded memory, unbounded input is the whole idea of the model.
(c) Contains 101. Four states tracking the longest prefix of 101 matched so far: none / 1 / 10 / 101 (accepting, absorbing). This is exactly what Knuth–Morris–Pratt builds → DSA.
2. Subset construction
Each DFA state is a set of NFA states. Start with (plus -closure), and for each symbol take the union of the NFA transitions.
Worst case is DFA states from NFA states, and it’s achieved: “strings whose -th symbol from the end is 1” needs an NFA of states and a DFA of — because a DFA must remember the last symbols, and there are possibilities.
Why it matters practically: it’s the trade behind regex engines. A DFA matches in but may take exponential space to build; simulating the NFA directly costs time and linear space. grep and RE2 choose the NFA simulation; backtracking engines choose neither and get exponential time → exercise 13.
3. is not regular
The quantifier order is the proof, so state it explicitly:
Assume regular. The pumping lemma gives a (adversary chooses). Choose (you choose, and ). The adversary decomposes with and (adversary chooses). Since , both and lie entirely within the leading s, so for some . Choose (you choose). Then , which has more s than s, so . Contradiction. ∎
You choose and ; the adversary chooses and the decomposition. Your must work against every legal decomposition — that’s why is chosen so that traps inside the s.
4. Pump the wrong thing
Try it on (all s before all s, counts unrelated — this is regular, matched by a*b*).
Take , and again . Pump: . Still in the language — and need not be equal. No contradiction. The proof simply fails to close.
The lesson: the pumping lemma is a one-way tool. It gives a necessary condition for regularity, not a sufficient one. Failing to derive a contradiction proves nothing — and there are non-regular languages that satisfy the pumping condition anyway. To prove regularity you must exhibit a DFA, regex or right-linear grammar; the Myhill–Nerode theorem is the tool that characterises it exactly.
5. Closure as construction
Intersection — the product construction. States are pairs ; run both machines in lockstep; accept when both accept. states. Union is identical but accepts when either does.
Complement of a DFA: swap accepting and non-accepting states. Trivial — but only because a DFA is total and deterministic, so every string has exactly one run.
For an NFA this fails. A string may have both accepting and rejecting runs, so swapping accept states gives the wrong language. You must determinise first — and pay the from exercise 2. That asymmetry is why regex engines supporting negation can blow up.
.
Part B — Context-free
6. Two grammars
Balanced parentheses:
Palindromes:
Both need the stack that a DFA lacks — matching nested structure requires unbounded counting, which is exactly what the pumping lemma rules out for regular languages.
7. Ambiguity
1 + 2 * 3 has two parse trees under : one grouping , one grouping . The grammar doesn’t say which, so the language is ambiguous and the “meaning” is undefined.
Stratify by precedence:
Now 1 + 2 * 3 has exactly one tree, yielding 7. Left recursion () gives left-associativity; the layering gives precedence.
This is what you do every time you write a grammar for a parser generator, and the shift/reduce conflicts such tools report are ambiguity being detected mechanically → parsing.
8. is not context-free
The CFL pumping lemma gives ; take ; the adversary picks with and .
Because , the window cannot span both s and s (they’re symbols apart). So:
- within one letter block ⇒ pumping changes one count, breaking equality
- straddles / ⇒ pumping changes s and/or s but never s
- straddles / ⇒ never touches s
In every case . ∎
The case analysis is the proof, and the constraint is what makes it finite. A pushdown automaton has one stack: it can match s against s, but by then it’s popped the information it would need for the s.
Part C — Computability and complexity
9. Turing machine for
The standard algorithm: mark the leftmost unmarked a (write X), scan right to the leftmost unmarked b (write Y), return left, repeat. Accept when no unmarked a and no unmarked b remain.
On aabb: XabY → XXYY → accept.
On aab: XaYb… second pass marks the remaining a, finds no unmarked b, rejects.
The tape is the unbounded memory a PDA’s stack couldn’t provide in the right shape — and note it does this in steps, which is a first taste of complexity distinct from computability.
10. Halting problem
Assume a total decider returning halts / loops. Build:
D(M): if H(M, M) says "halts": loop forever
else: halt
Now run :
- If says halts, then loops ⇒ it doesn’t halt. Contradiction.
- If says loops, then halts. Contradiction.
So cannot exist. ∎
The one-sentence version: is built to do the opposite of whatever it’s predicted to do, so asking it about itself makes the prediction self-refuting.
Same shape as Russell’s paradox and Cantor’s diagonal — self-reference plus negation. And it’s not an artefact: Rice’s theorem generalises it to every non-trivial semantic property of programs, which is why perfect static analysis of program behaviour is impossible in principle, not merely hard → compilers.
11. Reduce: “does this TM print z?”
Direction matters. To prove PRINTS-Z undecidable, assume it is decidable and use it to decide HALTING.
Given , build : run on with z erased from the alphabet (or renamed), and if ever halts, then print z.
prints z halts on . So a decider for PRINTS-Z gives a decider for HALTING, which doesn’t exist. ∎
The common error is reducing the wrong way — showing PRINTS-Z reduces to HALTING proves nothing about PRINTS-Z’s difficulty. You must reduce the known-hard problem to the new one: “if I could solve yours, I could solve this known-impossible one.”
12. 3-SAT ⇒ VERTEX COVER
Given a 3-CNF formula with variables and clauses:
- Variable gadget: for each variable, two vertices , joined by an edge. Covering it requires ≥1 vertex — that’s the truth assignment
- Clause gadget: for each clause, a triangle of three vertices labelled with its literals. A triangle requires ≥2 vertices
- Connection: edge from each clause-triangle vertex to the matching literal vertex
- Set
(⇒) Given a satisfying assignment: take the true literal from each variable pair (), and from each triangle take the two vertices whose literals are false (). Each connecting edge is covered — either by its triangle endpoint, or, for the one literal left out, by the variable vertex, which is true because the clause is satisfied. Total . ✓
(⇐) Given a cover of size : the gadgets force exactly 1 per variable pair and exactly 2 per triangle, with nothing spare. Read the assignment off the variable vertices. The uncovered triangle vertex’s connecting edge must be covered by its variable vertex, so that literal is true, so the clause is satisfied. ✓ ∎
Both directions are required. One direction shows only that a solution maps across; the other shows no spurious solutions appear. A “reduction” with one direction is a common and fatal error.
Part D — Build it
13. The regex engine
Thompson’s construction builds an NFA compositionally: literals are two states and an edge; concatenation joins them; alternation adds a branching start; * adds -loops. Subset construction determinises. Simulation walks the DFA in in the input, independent of the pattern’s shape.
The payoff is the comparison. On (a+)+$ against "a"*28 + "b":
| time | |
|---|---|
Python re (backtracking) | 23 seconds |
| Your Thompson NFA/DFA | microseconds |
Same regex. Same input. Different algorithm. A backtracking engine explores exponentially many decompositions; an automaton tracks the set of reachable states, and there are only finitely many. That’s why RE2 and Go’s regexp are linear-time by construction — and why they refuse backreferences, which take the language beyond regular → regular expressions · build your own.
Finishing this exercise makes the whole course concrete: you will have built the regex ≡ NFA ≡ DFA equivalence rather than read it.
14. DPLL
Unit propagation (a clause with one unassigned literal forces it), pure literal elimination (a variable appearing in one polarity can be set freely), then branch and recurse.
Unit propagation is by far the biggest win — typically the difference between minutes and milliseconds. Modern CDCL solvers add clause learning (on conflict, derive a new clause that prevents repeating the mistake) and non-chronological backtracking.
The practical upshot, which is the reason this exercise is here: SAT is NP-complete, and industrial solvers routinely handle instances with millions of variables. NP-complete means no known polynomial worst-case algorithm — not that instances you meet are hard. Confusing those two is the most common misuse of complexity theory in engineering arguments → note 07.
Related
Source: [reference] — the 23-second figure measured on Python 3.14, August 2026.
Software engineering
Infrastructure & security
Computer science
Hardware & engineering