Unit 2, Part 1 of 2 · CEUC302 Theory of Computation
A machine that can only remember so much
Chapter 1 ended with a claim: Leven needs almost no memory to recognise, and Leq needs an unbounded amount. This chapter makes "memory" a precise, countable thing — a finite set of states — and builds the machine that owns that memory: the finite automaton. One running example carries the whole chapter forward, Leven, alongside a new one built for contrast, Lends-ab — strings over {a,b} ending in "ab" — which turns out to need a genuinely different design instinct.
Circles and arrows
The picture everyone reaches for first
Double circle = accepting. Arrow into nowhere = start. Every state needs exactly one outgoing arrow per symbol.
q0 remembers "even a's seen so far," q1 remembers "odd." Reading a toggles between them; reading b changes nothing. This diagram is the automaton — not an illustration of it, the actual mathematical object, just drawn.
Before you start
This chapter assumes Chapter 1's vocabulary — language, grammar, the Chomsky hierarchy — and leans specifically on three things from it: Leven and Leq as running examples, the Type-3 grammar built for Leven in Section 1.3 (which becomes this chapter's first automaton almost unchanged), and the pigeonhole argument from Section 1.4 (which becomes this chapter's tool for proving a language needs more states than any machine you've tried has).
The smallest thing worth remembering
A state is not a place. It's a fact about everything read so far — specifically, the one fact that still matters for what's still to come.
Imagine reading a string over {a,b} one symbol at a time, left to right, with no way to look back and no way to look ahead. At every point you're allowed to jot down exactly one thing before the next symbol arrives — not the whole string so far, just one summary fact. For Leven, what's the smallest fact that's still enough to get the final answer right?
The intuition, no symbols yet
The answer is almost insultingly small: whether the number of a's seen so far is even or odd. Not which positions had a's. Not how many b's. Not the string itself. Just one bit. Every time an a arrives, flip the bit; every time a b arrives, leave it alone; at the end, "even" means accept. A state is exactly this — a name for one such summary fact — and a finite automaton is a machine built from a finite stock of them.
The formal treatment
A deterministic finite automaton (DFA) is a 5-tuple M = (Q, Σ, δ, q0, F):
- Q, a finite, non-empty set of states.
- Σ, the input alphabet (same idea as Chapter 1).
- δ : Q × Σ → Q, the transition function — from a state and a symbol, exactly one next state. Total, always — every state needs a defined move for every symbol, no exceptions and no "stuck."
- q0 ∈ Q, the start state.
- F ⊆ Q, the accepting states.
Reading one symbol is δ. Reading a whole string needs the extended transition function δ̂, defined by unwinding δ one symbol at a time:
The language of the machine is then simply L(M) = { w ∈ Σ* : δ̂(q0, w) ∈ F } — run the whole string from the start, check whether you land in an accepting state. A tiny worked instance: δ̂(q0, "ab") = δ(δ̂(q0,"a"), b) = δ(δ(q0,a), b). One layer at a time, δ̂ is nothing more than δ applied repeatedly — it looks heavier in symbols than it is in substance.
The design method, in one question
Building a DFA is answering, over and over: "do these two prefixes still need to be told apart?" If two different prefixes read so far would make every possible ending behave identically (same accept/reject outcome for every continuation), they can share a state. If some continuation exists that treats them differently, they need separate states. Leven needs exactly two states because exactly two things can be true about the a-count so far (even, odd) that ever matter to the final answer — not because {a,b} has two symbols, and not by any other coincidence.
Worked example · building and running Meven
Worked example
formalising Chapter 1's Type-3 grammar as a DFARun your own string
Meven, one symbol at a time
fig 2.1 · interactiveDon't confuse these
- δ is total. A real DFA never has a missing transition — every state names an outgoing move for every symbol, even if that move is "go to a dead state and stay lost." A diagram with an arrow missing isn't a smaller DFA; it's an incomplete one.
- δ and δ̂ are not the same size of question. δ answers "one symbol, from here, where next?" δ̂ answers "this whole string, from the start, where do I end up?" Confusing them is the single most common source of tracing errors under exam pressure.
- More states is not "more powerful." A 400-state DFA that happens to compute the same δ̂ outcomes as Meven's 2 states recognises the exact same language. Section 2.2 makes this precise and gives you a way to always find the smallest one.
Practice · 2.1
Seven problems
direct → variation → interpretation → synthesis2.1.1 · Trace Meven on "baab" state by state. Accept or reject?
Show solution
q0 →b q0 →a q1 →a q0 →b q0. Ends at q0 ∈ F — accept (2 a's, even, matches direct counting).
2.1.2 · Design a DFA for Lodd (odd number of a's) by changing exactly one part of Meven. Which part, and to what?
Show solution
Change only F: keep every state and every transition identical, set F = {q1} instead of {q0}. The machine still tracks the same fact (a-parity); only which parity counts as "success" changes.
2.1.3 · Variation: design a DFA for "the number of b's is even" (ignore a's entirely).
Show solution
Mirror image of Meven with the roles of a and b swapped: Q={r0,r1}, δ(r0,b)=r1, δ(r0,a)=r0, δ(r1,b)=r0, δ(r1,a)=r1, start=accept=r0.
2.1.4 · Variation: design a DFA for Lstarts-a = strings that begin with the symbol a (ε does not count). How many states, and why more than Meven's two?
Show solution
Three states. u0 (start, non-accept, "nothing read yet"), u1 (accept, "first symbol was a" — and it stays accepting forever after, regardless of what follows), u2 (reject, "first symbol was b" — stays rejecting forever). δ(u0,a)=u1, δ(u0,b)=u2, and both u1, u2 self-loop on both symbols. It needs a third state because "have I committed yet" is itself a fact that matters, on top of which way the commitment went — Leven never had a separate "not started yet" state because reading zero a's already correctly meant even.
2.1.5 · Interpretation: Meven finishes a run in q1. What, precisely, can you conclude?
Show solution
Only that this specific string is rejected (odd a-count) — nothing about any other string, and nothing about the machine's design being wrong. Ending in a non-accepting state is the correct, intended outcome for every string not in the language; it's evidence about the input, not a malfunction.
2.1.6 · Interpretation: a classmate builds a 5-state DFA for Leven and says "mine is smarter, it tracks more detail." Evaluate.
Show solution
Tracking more detail than the language ever asks for isn't "smarter" — it's redundant. If the 5-state machine still computes the same δ̂(q0,w) ∈ F verdict as Meven for every w, it recognises the identical language, just with wasted states. Section 2.2 gives a mechanical way to find and remove exactly this kind of redundancy.
2.1.7 · Synthesis (challenge) · Argue, without building a table, that no one-state DFA can recognise Leven.
Show solution
A single state q would have to be both the start state and would need δ(q,a) to equal q itself (nowhere else to go). Then every string of a's would end in the same state q, so "a" (odd, should reject) and "aa" (even, should accept) would get identical verdicts — they can't, since one must be accepted and the other rejected. One state cannot hold the two distinguishable facts ("even so far" vs "odd so far") that the language provably requires — a specific case of the general lower-bound argument Section 2.2 formalises.
Same machine, fewer states
Two states that no future input could ever tell apart are, for every purpose that matters, the same state. This one idea both shrinks machines and proves languages aren't regular at all.
Nothing stops someone from building a DFA for Leven with 5 states, or 50, all computing the exact same accept/reject verdicts as the 2-state Meven. The extra states aren't wrong, just wasteful. This section asks: how do you find the waste, and remove it, mechanically?
The intuition, no symbols yet
Picture two employees who, whatever question a customer asks next, always give identical answers — not because they coordinate, but because they hold identical information. You could fire one and nobody downstream would notice. Two DFA states are like this exactly when swapping one for the other, for every possible remaining input, never changes the final accept/reject verdict. States like this aren't almost the same. They're the same state wearing two name tags.
The formal treatment
Two states p, q are equivalent (written p ≡ q) if, for every string w ∈ Σ*, δ̂(p,w) ∈ F exactly when δ̂(q,w) ∈ F. Checking this directly needs testing infinitely many w — impossible by hand. The table-filling algorithm checks it in finitely many rounds instead, by looking for reasons two states must be different:
The logic behind round k+1 is just: if reading one more symbol a walks p and q into two states you've already proven distinguishable, then p and q were already distinguishable all along — that one symbol plus a later distinguishing string for the successor pair is a distinguishing string for p, q themselves.
Worked example · minimizing a redundant Leven machine
A 3-state machine that secretly only needs 2
fig 2.2a| pair | round 0 · accept status differs? | round 1 · leads to a distinguished pair? | verdict |
|---|---|---|---|
| (A,B) | yes — A accepts, B doesn't | — | distinguished |
| (B,C) | yes — C accepts, B doesn't | — | distinguished |
| (A,C) | no — both accept | on a: both → B (same); on b: both → C (same) — no new mark | equivalent |
No pair got a fresh mark in round 1, so the algorithm halts. A ≡ C; merge them into one state. What's left is exactly two states, one accepting, one not, with a flips to the other and b holds still — Meven from Section 2.1, recovered mechanically rather than designed by hand.
The same idea, run the other way · proving Leq isn't regular
Table-filling collapses states for a language that is regular. Run the indistinguishability idea directly on Leq, without assuming any machine exists yet, and it does something sharper: it shows no finite machine ever could.
Worked example
Myhill–Nerode argument for LeqDon't confuse these
- Equivalence needs agreement on every future string, not just one. Two states behaving identically on a single test input proves nothing; the table-filling algorithm works precisely because it checks this without literally trying every string.
- Minimization changes the machine, never the language. Meven and its bloated 3-state cousin recognise the exact same Leven — minimizing is bookkeeping cleanup, not a redefinition.
- Unreachable states need handling first. Table-filling only compares states that can actually be reached from q0; a state nothing ever transitions into should simply be deleted before you start, not fed into the table.
Practice · 2.2
Seven problems
direct → variation → interpretation → synthesis2.2.1 · A DFA has states {P,Q,R}: P and R both accepting, Q not. On symbol a: P→Q, Q→Q, R→Q. On symbol b: P→R, Q→Q, R→P. Run round 0 of table-filling. Which pair(s) are immediately distinguished?
Show solution
Round 0 only compares accept status: (P,Q) and (Q,R) are immediately distinguished (Q is the only non-accepting state). (P,R) survives round 0 (both accept).
2.2.2 · Continuing 2.2.1, run round 1 on the surviving pair (P,R). Do they merge?
Show solution
On a: P→Q, R→Q — same state, no new mark. On b: P→R, R→P — the pair (R,P) is just (P,R) itself, still unmarked at this point, so this also adds no mark. Round 1 marks nothing new ⇒ P ≡ R. The machine minimizes from 3 states to 2.
2.2.3 · Variation: minimize a DFA for Lodd built with a redundant extra state the same way Section 2.2's Leven example was (two accepting states with identical outgoing behaviour). What's the minimum state count?
Show solution
Two, by the identical argument with accept/reject roles swapped — Lodd still only has two Myhill–Nerode classes ("even so far," "odd so far"), regardless of which one is marked accepting.
2.2.4 · Variation: show directly that "a" and "b" are Myhill–Nerode distinguishable with respect to Leven.
Show solution
Take suffix z = a. "a"+"a" = "aa" ∈ Leven (2 a's). "b"+"a" = "ba" ∉ Leven (1 a). Same suffix, different outcomes — distinguished. (Consistent with them being routed to different states, q1 and q0, in Meven.)
2.2.5 · Interpretation: why does minimization never need to check infinitely many strings, even though the definition of state equivalence quantifies over all of Σ*?
Show solution
Because table-filling reduces "check all future strings" to "check one symbol, then reuse an already-computed answer about a shorter continuation" — each round only asks about single-symbol lookaheads into already-classified pairs. With finitely many states, there are only finitely many pairs and finitely many rounds before nothing new can be marked, so the whole infinite quantifier gets resolved in finite time.
2.2.6 · Interpretation: a classmate claims two states are inequivalent because they merely have different names. What's wrong?
Show solution
Names carry no information the machine can act on — only behaviour does. A and C in the worked example have different labels but identical accept status and identical transitions on every symbol; that behavioural match is the entire content of equivalence, and naming is irrelevant to it.
2.2.7 · Synthesis (challenge) · Adapt the ai/aj Myhill–Nerode argument to show {anbncn : n≥0} (Chapter 1, Section 1.3) is not regular.
Show solution
Consider a0, a1, a2, … again. For i ≠ j, take suffix z = bici. Then aiz = aibici ∈ the language, while ajz = ajbici has unequal a- and b-counts (j≠i) so it's excluded. Same suffix, different outcomes for every i≠j ⇒ infinitely many classes ⇒ not regular — identical proof skeleton, only the distinguishing suffix changed shape.
Machines allowed to guess
A new spine language for this section: Lends-ab, strings over {a,b} ending in "ab." It's exactly the kind of pattern a DFA finds awkward and a machine allowed to guess finds natural.
Try designing a DFA for Lends-ab by the Section 2.1 method — ask what each prefix needs remembered. Reading an a, you genuinely don't know yet whether it's about to be the start of a final "ab," or just another a in the middle somewhere. A DFA has to commit to one state anyway. A different kind of machine could instead try both possibilities at once, quietly dropping whichever guess stops paying off.
The intuition, no symbols yet
Picture several copies of yourself reading the same string in parallel, each free to make a different guess about what matters. One copy assumes nothing special is happening yet. Another copy, on seeing an a, bets "this is it — the start of the final ab" and watches for a b next. If the very next symbol is a instead, that particular copy's bet just failed and it quietly stops mattering (though a fresh copy can always start a new bet on that same a). The string is accepted if any copy is sitting in an accepting state when the input runs out.
The formal treatment
A non-deterministic finite automaton (NFA) is a 5-tuple exactly like a DFA's, with one change: δ : Q × Σ → P(Q) — from a state and a symbol, a set of possible next states (possibly empty, possibly more than one). Some treatments also allow ε-transitions (moving without consuming a symbol); this chapter's examples don't need them, but Section 2.4's RE-to-FA construction will. Running the machine on a string means tracking not one state but a whole set of active states, updated all at once:
The string is accepted the moment some thread, not necessarily all of them, ends up accepting. An empty active set (every thread has died) is simply a fast way to reach "reject" — there's no thread left to possibly succeed.
Building the NFA for Lends-ab
the NFA · 3 states, genuine branching
its subset-construction DFA · also 3 states, here
The violet arrow is the only genuinely nondeterministic move in the whole machine: from p0, reading a, the NFA goes to both p0 (ignore, keep waiting) and p1 (guess: this a starts the final ab) at once. Everything else is a single deterministic arrow. The right-hand diagram is what subset construction produces — each state is a set of NFA states, and D2 = {p0,p2} is accepting because it contains the NFA's accepting state p2.
Subset construction builds this DFA mechanically: start from {q0}, and for every reachable set S and symbol a, compute the new set ⋃p∈Sδ(p,a) as a single new DFA state; repeat until no new sets appear. Here it happened to produce exactly 3 states again — not a coincidence to rely on in general (see the note below), just a property of this particular language.
Worked example
tracing the NFA on "aab"Watch the active set move
every thread, all at once
fig 2.3 · interactiveWhy bother? Equivalence, and the succinctness trade
Theorem (NFA = DFA in power). Every NFA has an equivalent DFA (subset construction builds one), and every DFA is trivially already an NFA (one that never happens to branch). So allowing guesses adds no new languages beyond what DFAs already recognise — NFAs are a convenience, not extra power.
The convenience can be enormous, though
Subset construction can, in the worst case, turn an n-state NFA into a DFA with up to 2n states — one for every possible subset. The family "is the k-th symbol from the end an a?" makes this concrete and verified: a (k+1)-state NFA (guess where the window starts, then count k symbols) faces a DFA that provably needs 2k states (it must remember the last k symbols exactly, as there's no shortcut summary). At k=3 that's 4 NFA states against 8 minimal DFA states — small here, but the gap doubles with every additional k. Lends-ab just happens to be a case where the blow-up doesn't occur; don't expect that to be typical.
Don't confuse these
- Reject means every thread failed, not one thread failed. A single dead thread is routine — other threads may still be alive and heading toward acceptance.
- An empty active set is a valid, ordinary outcome. It just means every thread has died; treat it as "definitely reject from here on," not as an error.
- "NFAs are more powerful" is the wrong lesson. The equivalence theorem says the opposite: same language class, different convenience. What changes is how easy the design is, and (sometimes) how few states it takes.
Practice · 2.3
Seven problems
direct → variation → interpretation → synthesis2.3.1 · Trace the NFA's active set through "baba." Accept or reject?
Show solution
Start {p0}. Read b: {p0}. Read a: {p0,p1}. Read b: p0→{p0}, p1→{p2}, union {p0,p2}. Read a: p0→{p0,p1}, p2→{p1}, union {p0,p1}. Final {p0,p1} has no p2 — reject (correct: "baba" ends in "ba," not "ab").
2.3.2 · Trace the subset-construction DFA (D0,D1,D2) on the same string "baba" and confirm it agrees with 2.3.1.
Show solution
D0 →b D0 →a D1 →b D2 →a D1. Final D1 is not accepting — reject, matching 2.3.1 exactly. Two different-looking machines, identical verdict on every input — that's what "equivalent" means in practice.
2.3.3 · Variation: sketch an NFA (states and transitions, no need to draw) for "contains the substring aa," using the same guessing trick.
Show solution
States {r0,r1,r2} (accept). r0→a{r0,r1} (keep waiting, or guess this a starts "aa"), r0→b{r0}. r1→a{r2} (guess confirmed), r1→b∅ (guess failed, thread dies). r2 self-loops on both symbols (once "aa" is seen, stay accepting regardless of what follows). Structurally identical to Lends-ab's NFA with the guess-confirmation symbol changed from b to a.
2.3.4 · Variation: a 2-state NFA has t0 (start) with δ(t0,a)={t0,t1}, δ(t0,b)={t0}, and t1 (accept) with no outgoing transitions at all. What language does it recognise, and how many states does subset construction produce?
Show solution
t1 has no way out, so a thread only survives to the end by branching into t1 on the very last symbol read — this recognises "strings ending in a" (length ≥1). Subset construction gives exactly 2 states: E0={t0} and E1={t0,t1} (accepting), with E0→aE1, E0→bE0, E1→aE1, E1→bE0.
2.3.5 · Interpretation: after reading some prefix, the NFA's active set is ∅. Three more symbols arrive. What's the active set now, and why is no further work needed?
Show solution
Still ∅ — the union of δ(p,a) over an empty set of states p is itself empty, for any symbol. Once every thread has died there is nothing left to branch from, ever again; the string is doomed to rejection regardless of what still arrives. (This is exactly why a DFA needs an explicit dead state to represent the same situation — δ must be total, so it can't just "have nothing.")
2.3.6 · Interpretation: a classmate says "since NFAs can't be built in real hardware, they're a purely theoretical toy." Push back on this.
Show solution
NFAs are routinely simulated in software (tracking the active set exactly as this section does) whenever avoiding subset construction's potential blow-up matters — this is precisely how backtracking regex engines (Python's re, PCRE, JavaScript) work internally, exploring branches directly rather than pre-computing every subset. "Not physically one circuit" doesn't mean "not implemented"; it means implemented a different way, with its own trade-offs (Chapter 3 touches the catastrophic-backtracking downside of this choice).
2.3.7 · Synthesis (challenge) · Using the verified k=3 numbers (4-state NFA, 8-state minimal DFA for "3rd symbol from the end is a"), explain in your own words why the NFA's guess-based design sidesteps needing to remember a whole window of symbols.
Show solution
The DFA has no way to "guess" which position is 3-from-the-end until the string actually ends, so it's forced to carry the last 3 symbols forward at every step, just in case the string ends right there — and there are 23=8 possible 3-symbol windows, hence 8 states. The NFA sidesteps this by not committing: at every a, one thread bets "this is the one" and just counts down k symbols, while a separate always-alive thread keeps scanning for a better bet. Betting once per candidate position is cheap (k+1 states); remembering the whole window unconditionally, so that any future ending can be checked, is what costs the DFA exponentially more.
The recipe and the machine are the same power
Everything built by hand in this chapter — DFAs, NFAs — turns out to be exactly as expressive as a small, human-writable notation: the regular expression.
A DFA is precise but tedious to write down for anything beyond a few states. A regular expression (RE) is the opposite: compact, readable, and the thing a human actually types into a lexer specification or a search box. Kleene's theorem is the guarantee that nothing is lost switching between them.
The intuition, no symbols yet
A regular expression is built from exactly three moves: do this, then that (concatenation), do this or that (union), and do this any number of times, including zero (star). That's the entire vocabulary. Every regular language, no matter how it was first described, turns out to be reachable using nothing but these three moves applied to single symbols.
The formal treatment
Regular expressions over Σ are defined recursively. Base cases: ∅ (denotes the empty language, no strings at all), ε (denotes {ε}), and each a ∈ Σ (denotes {a}). Inductive cases, for REs R and S:
| notation | name | language |
|---|---|---|
| R* | star (Kleene closure) | L(R)* = {ε} ∪ L(R) ∪ L(R)L(R) ∪ ··· |
| RS | concatenation | L(R)L(S) = {uv : u∈L(R), v∈L(S)} |
| R+S | union | L(R) ∪ L(S) |
Star binds tightest, then concatenation, then union — exactly like exponents,
multiplication, and addition in ordinary algebra. a+bc* parses as
a + (b(c*)), never as (a+b)(c*). Two REs
already verified in this chapter's spine:
Don't confuse these
- ∅ is not ε. The RE ∅ describes a language with zero strings; the RE ε describes a language with exactly one string, the empty one. Same relationship as Chapter 1's ∅-vs-{ε} trap, one level up.
- (a*b*) is not (a+b)*.
a*b*only matches strings that are some a's followed by some b's, with no interleaving — "ba" fails it.(a+b)*matches every string over {a,b} whatsoever. Losing the parentheses around the union changes the language completely, not just the notation.
Kleene's Theorem
Kleene's Theorem. A language is regular if and only if some regular expression describes it. Both directions are constructive:
RE → FA
Build the machine by structural induction on the expression: a tiny 2-state fragment for
each base case (one edge labelled a, or an ε-edge, or no edge at all for ∅),
then glue fragments together following the last operator applied — concatenation wires
one fragment's exit into the next's entry, union adds a new entry that ε-branches to
both fragments, and star adds an ε-edge looping the exit back to the entry (plus a
bypass, so zero repetitions is allowed). This is exactly how every DFA and NFA built by hand
in Sections 2.1 and 2.3 could instead have been produced mechanically from
b*(ab*ab*)* or (a+b)*ab — this chapter
just built them directly, since direct construction is faster for a human and the mechanical
version is what a compiler needs.
FA → RE, by state elimination
Going the other way: add a new start S with an ε-edge to the old start, add a new final F with ε-edges from every old accepting state, then delete the old states one at a time. Deleting a state q rewires every incoming-edge/outgoing-edge pair around it, multiplying in q's own self-loop (starred, since the loop can fire any number of times):
before elimination · Meven with bookkeeping S, F added
fig 2.4Worked example
eliminating q1, then q0Different elimination orders, different-looking (equally correct) answers
Eliminating q0 before q1 above would have produced a different intermediate expression
on the way to an equally valid final RE. This is normal, not a sign of a mistake —
Regular expressions for the same language are almost never unique, the same way
2×3 and 1+5 are different-looking
correct answers to "what's six." When two REs look different, testing both against the
same handful of strings (or, more rigorously, converting both to minimal DFAs and
comparing) is how you'd confirm they secretly agree.
Practice · 2.4
Seven problems
direct → variation → interpretation → synthesis2.4.1 · By hand, check "b", "aa", and "ab" against b*(ab*ab*)*. Which match?
Show solution
"b": matched entirely by the leading b*, with the starred group firing zero times. Matches. "aa": leading b* matches nothing; one firing of (ab*ab*) with both b*'s empty consumes "a"+"a". Matches. "ab": leading b* matches nothing; one firing needs a, then some b's, then a SECOND a — but only one a is available before the string ends. No way to complete a firing. Does not match — correctly, since "ab" has an odd a-count.
2.4.2 · Write a regular expression for Lstarts-a (strings beginning with a).
Show solution
a(a+b)* — the required first a, then anything at all afterward.
2.4.3 · Variation: write a regular expression for "contains aa as a substring."
Show solution
(a+b)*aa(a+b)* — anything, then the required aa, then anything. (Verified against the direct substring test for all strings up to length 12 with zero mismatches.)
2.4.4 · Variation: for Lodd's GNFA (same shape as Meven's but F={q1}), eliminate only q0 (not q1) and give the resulting intermediate GNFA's edges.
Show solution
q0's incoming: S via ε, and q1 via a. q0's outgoing: q1 via a. Self-loop: b. Two new edges appear: S→q1 labelled b*a (from the S/ε pair), and q1's self-loop gains ab*a (from the q1-via-a pair), unioned with its existing b self-loop to give b+ab*a. One more elimination (of q1) would finish the job.
2.4.5 · Interpretation: two students eliminate the same GNFA in different orders and get RE1 ≠ RE2 as text. How would you settle whether both are correct?
Show solution
Textual difference proves nothing by itself. Test both against a shared batch of strings (including tricky short ones like ε), or — conclusively — convert both REs back to DFAs and check the two DFAs are equivalent (same minimized machine, via Section 2.2). Matching on a finite test batch is good evidence but only full conversion, or a formal equivalence proof, is a guarantee.
2.4.6 · Interpretation: is a*b* the same language as (a+b)*? Settle it with one witness string.
Show solution
No. "ba" ∈ (a+b)* (it's some string over {a,b}) but "ba" ∉ a*b* (a* can match zero a's, but then b* would need to consume "ba" starting with b, fine for the b, but then the trailing "a" has nowhere left to go since b* can't match an a and there's no more a* left to consume it afterward). One witness string is enough to separate two languages; it's never enough to prove two languages equal.
2.4.7 · Synthesis (challenge) · Explain, referencing CO1, why Kleene's theorem being a two-way equivalence matters for building a lexical analyser specifically — not just as abstract elegance.
Show solution
A language designer writes token rules as regular expressions — short, readable, easy to review (e.g. an identifier as letter(letter+digit)*). Kleene's theorem guarantees each such RE has an equivalent DFA, so a lexer-generator (flex, and similar tools) can mechanically convert the human-friendly RE into the machine-friendly DFA, then minimize it (Section 2.2) for speed. Without the RE→FA direction, every token pattern would have to be hand-built as a state machine; without the FA→RE direction, there'd be no way to double check or document what an existing scanner's states actually mean. Both directions are load-bearing for the same real pipeline.
Cheat sheet
One line per idea. If a line doesn't ring a bell, that section needs a re-read before Chapter 3.
DFA · 2.1
M = (Q,Σ,δ,q0,F) — δ total, one move per symbol
δ̂ — whole-string version, built by unwinding δ
L(M) = {w : δ̂(q0,w)∈F}
design rule: separate states only for prefixes some future string would tell apart
Minimization · 2.2
p≡q — agree on every future string, not just one
table-filling — mark by accept-status, then by leading to marked pairs
Myhill–Nerode — # states needed = # indistinguishable-prefix classes
infinitely many classes (like a0,a1,… for Leq) ⇒ not regular
NFA & subset construction · 2.3
δ : Q×Σ → P(Q) — a set of next states, not one
accept iff some thread ends in F; ∅ active set = dead, ordinary reject
subset construction — each DFA state = a set of NFA states
NFA ≡ DFA in power; worst case n states → up to 2n
RE & Kleene's theorem · 2.4
star > concatenation > union — binding order, tightest first
∅ = no strings; ε = one string, the empty one
RE → FA: build small fragments, glue by the outermost operator
FA → RE: state elimination, X→Y gains Rin(Rloop)*Rout
Ten questions, no section labels
Exams don't tell you which lecture a question came from. Neither does this.
ST1 · Trace Meven on "bbab." Accept or reject?
Show solution
q0→bq0→bq0→aq1→bq1. Final q1 — reject (1 a, odd).
ST2 · True or false: a DFA is allowed to leave some state's transition on some symbol undefined.
Show solution
False. δ must be total — every state needs a defined move for every symbol in Σ, even if that move leads to a permanent-reject dead state.
ST3 · Are "aa" and "bb" Myhill–Nerode distinguishable with respect to Leven?
Show solution
No, they're equivalent. Both have an even a-count (2 and 0). Appending any suffix z adds the same number of a's to both, so "aa"z and "bb"z always share the same a-count parity — no suffix can ever split them. Both route to q0 in Meven.
ST4 · Worst case, how many DFA states can subset construction produce from an n-state NFA?
Show solution
Up to 2n — one for every possible subset of the n NFA states (verified concretely at n=4 giving 8 minimal DFA states, Section 2.3).
ST5 · Parse a+b*c using standard RE precedence. Is it (a+b)*c, a+(b*c), or something else?
Show solution
a+(b*c). Star binds to b alone first, then concatenates with c, and union (the loosest-binding operator) applies last across the whole thing.
ST6 · True or false: every DFA is also, technically, an NFA.
Show solution
True. A DFA's δ(q,a) is just a special case of an NFA's δ(q,a) where the resulting set always happens to have exactly one element. Nothing needs to change to view any DFA this way.
ST7 · A DFA has two accepting states with identical outgoing transitions on every symbol. Equivalent or not?
Show solution
Equivalent. Same accept status, and every symbol leads them to the same place (or behaviourally-identical places) — that's exactly the table-filling criterion for merging, with zero rounds of new marks possible.
ST8 · Give a regular expression for the empty language, and a separate one for the language containing only the empty string.
Show solution
Empty language: ∅. Language {ε}: ε. Different symbols, different languages, easy to mix up under exam pressure (Section 2.4's trap box).
ST9 · An NFA's active set after reading a prefix is {p1,p2}, and p2 is the only accepting state. If the input ended right now, accept or reject?
Show solution
Accept. The active set intersects F (via p2) — that's the entire acceptance condition; p1 being non-accepting doesn't matter once some thread qualifies.
ST10 · Section 2.2 shows Leq has infinitely many Myhill–Nerode classes. Does that mean "no DFA recognises Leq," or "no finite DFA recognises it" — and is there a difference?
Show solution
No difference — a DFA's state set Q is required finite by the very definition in Section 2.1, so "no finite DFA" and "no DFA at all" say exactly the same thing. There's no such object as an "infinite DFA" to fall back on within this course's definitions; that's precisely why the infinite-classes argument is a complete proof of non-regularity, not a partial one.
Where this goes next
- Chapter 3 proves Leq's non-regularity a second way — the formal Pumping Lemma — and uses it on languages Myhill–Nerode makes awkward.
- Closure properties (union, intersection, complement, concatenation, star) for regular languages get their own full treatment, each with a construction.
- Lends-ab's whole design pattern — guess, confirm, absorb — reappears directly in Chapter 3's DFA-based lexical scanners.
Further reading
- Sipser, Introduction to the Theory of Computation, 3rd ed. — the regular languages chapter covers DFA/NFA equivalence and Kleene's theorem in the same order used here, with the standard state-elimination write-up (Sipser calls the intermediate machine a GNFA, the term borrowed above).
- J. C. Martin, Introduction to Languages and the Theory of Computation. — its treatment of the Myhill–Nerode theorem is a good second angle on Section 2.2, with different worked languages than the ones used here.
Next: Chapter 3 · Finite Automata II — Closure Properties, Pumping Lemma & Lexical Analysis