You have two finite automata over the same alphabet; how do you build one recogniser that accepts exactly the strings both accept?
answer
- run both at once
- one bookkeeper per machine
- pairs, not a sum
- accepting set is the only knob
- missing edges kill the pair
basics
~20 sRun both machines at once. The product automaton's states are pairs (p, q), one component per machine, and each input symbol advances both components. Mark a pair accepting when both components accept, and you have the intersection.
solid answer
~50 sBuild the **product machine**. Its states are pairs `(p, q)` where `p` is a state of the first machine and `q` a state of the second; the start state is the pair of the two start states; and on symbol `a` the pair steps to `(step1(p, a), step2(q, a))`, so one symbol advances both components in lockstep. After reading any string, the pair holds exactly where each machine would be on its own. Then the accepting set is the only knob: accept when both components accept for intersection, when either does for union, and when the first does but the second does not for difference. The state count is at most the product of the two, and in practice you explore only the reachable pairs. Both machines must be total first — a missing transition leaves the pair with nowhere to go.
code
pseudocode · 14 linesstart_pair <- (start1, start2)
seen <- { start_pair }
worklist <- [ start_pair ]
while worklist is not empty:
(p, q) <- remove oldest from worklist
if accepting1(p) and accepting2(q):
mark (p, q) accepting // intersection
for each symbol a in alphabet:
nxt <- (step1(p, a), step2(q, a))
add edge (p, q) --a--> nxt
if nxt not in seen:
add nxt to seen
append nxt to worklistgo deeper
Recall the shape: one machine can simulate two by remembering a pair of positions, one per original machine. Knowing that boolean combinations of recognisers are themselves recognisers is enough at this stage.
Explain the pairing precisely: start pair, lockstep transition, and the accepting set as the only thing that changes between union, intersection and difference. State the invariant about where each component sits after reading a prefix.
Show that you have implemented it: explore reachable pairs lazily, complete both machines with a trap state first, and know that the union condition is wrong on partial or nondeterministic inputs.
Frame it as a cost decision. The product is polynomial and safe to apply repeatedly; determinisation is not. Sequencing boolean operations so the expensive one happens once, on the smallest operand, is what keeps a rule pipeline affordable.
## The problem You own two recognisers over the same alphabet — say a gateway where one finite automaton accepts every message matching an allow rule and another accepts every message matching a deny rule — and you need a single machine whose verdict is a boolean combination of theirs. You cannot chain them: each must see the **whole** input from the beginning, symbol by symbol. The **product construction** solves this by running both simultaneously inside one machine, and it is the workhorse behind closure of the regular languages under all the boolean operations. ## The construction Let the machines be `M1 = (Q1, A, step1, s1, F1)` and `M2 = (Q2, A, step2, s2, F2)` over the same alphabet `A`. The product machine is: - **States**: every pair `(p, q)` with `p` in `Q1` and `q` in `Q2`. The first component remembers where `M1` would be, the second where `M2` would be. - **Start state**: `(s1, s2)`. - **Transition**: `step((p, q), a) = (step1(p, a), step2(q, a))` — one symbol advances *both* components. - **Accepting set**: any boolean condition you like on the two components. The invariant, provable by a one-line induction on input length, is that after reading a string `w` the product sits in `(p, q)` exactly when `M1` alone would sit in `p` and `M2` alone in `q`. Everything else follows from choosing which pairs accept. ## Picking the accepting set | language you want | accepting pairs | |---|---| | intersection | `p` in `F1` **and** `q` in `F2` | | union | `p` in `F1` **or** `q` in `F2` | | difference (first minus second) | `p` in `F1` **and** `q` not in `F2` | | symmetric difference | exactly one of the two holds | States and transitions are identical in all four rows; only the accepting set changes. A candidate who describes four unrelated constructions has memorised rather than understood. ## Completeness is a precondition, not a detail The lockstep step is defined only when **both** machines have an outgoing transition on the current symbol. If either is partial — a missing edge, meaning it would silently reject — the pair has nowhere to go and the product rejects. - For **intersection** that is harmless: a string the partial machine rejects is not in the intersection anyway. - For **union** it is a real bug: the string may still be accepted by the machine that is alive, and the product loses it because its partner died. The boring fix comes first: add one non-accepting **trap state** to each machine and route every missing edge to it, so every state has an outgoing edge on every symbol. Then all four rows of the table are correct. Nondeterminism carries the same warning in a sharper form. Pairing two **nondeterministic** machines still gives intersection, because "there is a joint run that accepts" is exactly "there is an accepting run in each". It does **not** give union, because union asks about *separate* runs of the two machines and the pair forces them to proceed together. For union of nondeterministic machines, take the disjoint union of the two state sets with a fresh start state that can silently enter either original start. ## Size and cost - The state count is **at most `|Q1| x |Q2|`** — a product, not an exponential. This is the cheap closure operation, which is why it sits underneath equivalence testing and rule composition. - You rarely materialise all of it. Explore pairs lazily from `(s1, s2)` and keep only the reachable ones; for unrelated rules that is usually a small fraction of the worst case. - Work is proportional to reachable pairs times alphabet size, so a machine over byte values costs 256 edges per pair unless you store symbol ranges on edges. - The result is **correct, not minimal**. Reducing it to the smallest equivalent machine is a separate algorithm with its own cost. ## What the interviewer is listening for 1. That you say **pairs of states** without hesitating, and can state the invariant about where each component sits after reading `w`. 2. That you notice the accepting set is the only difference between union and intersection. 3. That you volunteer the completeness precondition before being asked, because that is the part that actually breaks in code. 4. If the conversation goes further: that the product is polynomial while complementing a nondeterministic machine is not, so the **order** in which you apply closure operations decides whether the pipeline is affordable.
- How do you build a recogniser for the reversals of the strings a finite automaton accepts?Reverse every transition, add a fresh start state with silent moves into all the old accepting states, and make the old start state the sole accepting state. A string is accepted exactly when its reversal was. The result is nondeterministic even when you started from a deterministic machine, because reversed edges can share a source and a symbol.
- Does the product construction still work when one of the two machines is nondeterministic?For intersection, yes: a joint accepting run of the pair is exactly an accepting run in each machine. For union it fails, because a pair dies as soon as either component has no move, losing strings the other would have accepted. Build union instead from a fresh start state with silent moves into both original start states.
- Why is the reachable part of a product machine usually far smaller than the worst-case bound?Most pairs are never simultaneously reachable: the two machines' progress is correlated by the same input, so only pairs consistent with some common prefix appear. Exploring lazily from the start pair keeps just those. The bound is tight only for rules deliberately built to be independent, such as counting the input modulo two coprime numbers.
Two proofreaders read the same page in lockstep, each keeping their own place in their own checklist. The page is stamped only when both finish satisfied — and if one of them walks out halfway, the pair stops, which is why neither is allowed to have a missing step.
saying these in an interview costs you the question
- Runs the first machine to completion, then feeds its verdict into the second
- Thinks the product needs as many states as the two machines added together
- Uses the same accepting set for union and for intersection
- Ignores missing transitions, so a dead component silently kills a union
- Claims the product construction yields the smallest possible machine
- Believes intersecting two finite automata needs exponentially many states