The problem: one machine, two demands
In the last guide you got fluent at designing a DFA for a single pattern — strings with an even number of a's, strings ending in b, strings whose length is a multiple of three. Each time, the trick was the same: figure out the one fact you must remember, and let the states be the finite list of possible answers. But real specifications are rarely a single condition. A filter might want strings that have an even number of a's and end in b. A compiler check might want an identifier that starts with a letter and contains no two dots in a row. Two demands, one machine. How?
The naive instinct is to sit down and invent a single clever machine that watches for both things at once. Sometimes you can, but it is fiddly and error-prone, and it gets exponentially worse as you add more conditions. There is a far better idea, and it is almost embarrassingly simple: do not build one machine watching for two things. Build the two machines you already know how to build, then run both of them at the same time, in lockstep, inside a single combined machine. That combined machine is what the product construction produces.
Two machines in one head: pairing the states
Here is the picture. Imagine you carry two little turnstiles in your head. Machine A tracks the parity of a's: it has two states, call them Even and Odd, and every a flips it while every b leaves it alone. Machine B tracks the last symbol: it has two states, SawA and SawB, jumping to SawA on an a and SawB on a b. Now read the input string just once, but feed each symbol to BOTH machines simultaneously. At every moment your full mental state is a pair: (where A is, where B is) — for instance (Even, SawB).
That pair is itself a single state of a brand-new DFA. If A has 2 states and B has 2 states, the combined machine has at most 2 times 2 = 4 states, one for each pairing: (Even,SawA), (Even,SawB), (Odd,SawA), (Odd,SawB). This set of all pairs is exactly the Cartesian product of A's states with B's states — which is why the whole technique is named the product construction. The combined start state is the pair of the two original start states, and each combined transition just lets both halves take their own step at once.
Building it precisely
Let us write it as a recipe. Say A has transition function deltaA and B has transition function deltaB, both over the same alphabet Sigma (the Greek capital Σ, your fixed symbol set). The product machine's states are all pairs (p, q). Its transition on a symbol x is defined component-wise: delta((p, q), x) = (deltaA(p, x), deltaB(q, x)) — A's part moves by A's rule, B's part moves by B's rule, both reading the very same x. That single line is the whole engine.
Everything so far is identical no matter which logical connective you want. The ONLY thing that changes is which pairs you declare to be accept states. Want A and B (the intersection of the two languages)? Accept a pair (p, q) exactly when p is accepting in A AND q is accepting in B. Want A or B (the union)? Accept when p is accepting in A OR q is accepting in B. Want 'in A but not in B' (set difference)? Accept when p accepts but q does not. The machinery is the same; you are just choosing a rule over the two component verdicts.
A: even number of a's B: ends in b (start = SawA, accepts SawB)
states {Even, Odd} states {SawA, SawB}
on a: flip on b: stay on a: -> SawA on b: -> SawB
PRODUCT for "even a's AND ends in b" (start = (Even, SawA))
state on a on b accept? (AND)
--------------- ----------------- ----------------- ----------------
(Even, SawA) (Odd, SawA) (Even, SawB) no (not ends-b)
(Even, SawB) (Odd, SawA) (Even, SawB) YES (even & ends-b)
(Odd, SawA) (Even, SawA) (Odd, SawB) no (odd a's)
(Odd, SawB) (Even, SawA) (Odd, SawB) no (odd a's)
trace "abab": (Even,SawA) -a-> (Odd,SawA) -b-> (Odd,SawB)
-a-> (Even,SawA) -b-> (Even,SawB) => accept (1 of 4 states)The deep payoff: closure properties
Step back and notice what you have actually proved. If A recognizes a regular language L1 and B recognizes a regular language L2, then the product machine is a genuine, finite DFA that recognizes their intersection (or union, or difference). So the intersection of two regular languages is itself regular — it cannot escape the family. The same construction, with a different accept rule, shows union is regular too. These guarantees are called the closure properties of the regular languages: the family is closed under intersection and union, meaning you can never leave it by combining two members.
Complement is even easier and needs no product at all. Given a DFA for L, just flip every state's verdict: every accept state becomes non-accepting and vice versa. The new machine accepts exactly the strings the old one rejected, so the complement of a regular language is regular. This is the complement construction, and it works because a DFA is total and deterministic — on every string it lands in exactly one well-defined state, so 'rejected' and 'accepted' partition the strings cleanly with no gaps.
What the product can and cannot buy you
Be honest about the cost. Combining a machine of m states with one of n states gives up to m times n paired states — the count multiplies. Two conditions of 5 states each give 25; chain four of them and you are near 600. This blow-up is in the number of states, not in running time: you still read the input just once, taking a single step per symbol, so a product DFA decides membership in time proportional to the input length, the same as any DFA. The product is cheap to run and only pricey to write down.
And here is the boundary you must respect. The product lets you combine conditions that are each already regular. It does not, and cannot, give a DFA extra counting power. You can intersect 'even number of a's' with 'even number of b's' — both regular, so their intersection is regular. But you can NOT use the product to build a DFA for 'the number of a's equals the number of b's,' because that is not a combination of finite-memory conditions; it demands remembering an unbounded count, which runs straight into the finite-memory limit of any DFA. The product is a way to combine within the regular world, never a way to break out of it — and exactly why a DFA can never count without bound is the subject of the next guide.