Product Constructions: Intersection, Union, and Complement Without Rebuilding

Regular languages are closed under union, intersection, complement, concatenation, and star. Closure under the boolean operations is not proved by an induction on expressions or by an argument about strings; it is proved by building a machine. The construction pairs states, and the pairing is the entire mechanism: two machines run in lockstep on the same input, and a state of the product records what each of them would have concluded.

The construction is worth understanding at the level of table layout, because it is used constantly in practice for exactly the reason it exists in theory: it lets a tool combine specifications without converting either one back to a regular expression.

Running two machines at once

Given M₁ = (Q₁, Σ, δ₁, q₁, F₁) and M₂ = (Q₂, Σ, δ₂, q₂, F₂), the product machine has state set Q₁ × Q₂, start state (q₁, q₂), and transition δ((p, q), a) = (δ₁(p, a), δ₂(q, a)). The accepting set is chosen according to the operation:

Operation	Accepting states
Intersection	F₁ × F₂
Union	(F₁ × Q₂) ∪ (Q₁ × F₂)
Difference	F₁ paired with states outside F₂
Symmetric difference	pairs where exactly one component is accepting

The union rule is the one that surprises people. Accepting a pair when either component accepts looks like it answers a different question, because each component has been following its own transition function the whole time. It is in fact the union of the two languages: the product consumes the whole input in lockstep, so at the end the pair’s components are exactly the states each machine would have reached on that input alone, and the pair is accepting precisely when at least one of those states is accepting.

The reachable part of the product is usually much smaller than |Q₁| · |Q₂|. The construction should explore from the start pair rather than allocate the full cross product, for the same reason the subset construction explores reachable subsets: unreachable pairs are states that no input reaches, and they only inflate the table.

from collections import deque

def product(d1, d2, start1, start2, acc1, acc2, op, nsym):
    start = (start1, start2)
    index, order, queue = {start: 0}, [start], deque([start])
    rows = []
    while queue:
        p, q = queue.popleft()      # FIFO: processing order matches discovery order
        row = []
        for a in range(nsym):
            nxt = (d1[p][a], d2[q][a])
            if nxt not in index:
                index[nxt] = len(order)
                order.append(nxt)
                queue.append(nxt)
            row.append(index[nxt])
        rows.append(row)
    if op == "and":
        acc = [acc1[p] and acc2[q] for p, q in order]
    elif op == "or":
        acc = [acc1[p] or acc2[q] for p, q in order]
    else:
        acc = [acc1[p] and not acc2[q] for p, q in order]
    return order, rows, acc

The accepting predicate is computed after exploration because it depends on the numbering assigned during exploration. Computing it inline is possible but requires the final indices, which the dictionary does not have until the pair is first seen.

Complement needs a total function

Complement is the operation that does not fit the pattern. It is not a product of two machines; it is a single machine with F replaced by Q \ F. That one-line change is correct only if the transition function is total.

The reason is that a partial machine has an implicit third outcome. When a transition is missing, the run stops without reaching any state, and the string is rejected. Flipping the accepting set does not change that: the run still stops, still rejects, and the complement of a rejected string should be accepted. A machine that rejects by crashing cannot be complemented by relabelling its states.

The fix is to add a dead state, route every missing transition to it, and make it non-accepting with self-loops on every symbol. Then every run reaches a state, and the accepting set can be flipped. The dead state is also the state that any complement must have: the strings that lead nowhere in the original are exactly the strings the complement accepts, and they need somewhere to live.

This is why the textbook definition of a DFA insists on totality. It is not pedantry about the five-tuple; it is the precondition that makes complement a state relabelling rather than a construction. A library that stores partial tables and offers a complement operation has to perform the completion first, and that completion changes the state count by one before the operation even starts.

Sizes and the cost of combining

The product has at most |Q₁| · |Q₂| states, and the bound is attained: two machines whose state sequences are independent under every input can be paired into a machine with the full cross product reachable. A 100-state machine and a 200-state machine produce at most 20,000 states, which with 4-byte entries and a 64-symbol alphabet is 20,000 rows of 256 bytes, 5 MB of table.

The product also multiplies the alphabet work: each product state has |Σ| outgoing transitions, and each transition is two lookups in the component tables. The time to build the product is proportional to the number of reachable pairs times the alphabet size, so the construction is usually memory-bound rather than compute-bound.

Chaining operations compounds the cost. Intersecting three machines pairwise gives a machine of size at most |Q₁| · |Q₂| · |Q₃|. This is the mechanism behind the state explosion in model checking: a system described as the product of k components, each with a handful of states, has a reachable state space that grows with the product of the component sizes, and the growth is genuine rather than an artifact of the construction.

Minimizing after each product is the standard mitigation, and it is not optional in a toolchain that chains several operations. The product of two minimal machines is generally not minimal, and the redundancy compounds. The refinement pass described in partition refinement costs O(n log n) in the product size and typically removes a large fraction of the pairs.

Composing with determinization

The product construction assumes both inputs are deterministic. Given two NFAs, determinizing each first is the general route, and the worst-case size bound then becomes 2^{|Q₁|} · 2^{|Q₂|}, which is worse than determinizing the product of the NFAs would have been. A product construction over the nondeterministic machines themselves is not available in general, because the accepting condition at the end of the input must account for every surviving alternative in both machines, and that is what determinization computes.

For intersection specifically, there is a cheaper route that skips determinization of the components: the intersection of two NFA languages can be accepted by an NFA whose states are pairs of NFA states, with transitions taken synchronously on symbols and epsilon moves allowed in either component alone. That machine has |Q₁| · |Q₂| states and no exponential, at the cost of being nondeterministic. For union, the disjoint union of the two NFAs with a new start state works, and for concatenation the fragments are joined by an epsilon transition. These are the closure constructions that a regular expression engine uses, and they are why closure under boolean operations does not require determinization in a Thompson-style construction.

The trade is the same one that runs through the whole subject: determinism gives a fast simulation and a simple complement, nondeterminism gives small machines and cheap composition. The product construction sits on the deterministic side, and the NFA constructions sit on the other.

Where the construction is used in practice

Firewall and routing rule sets are the clearest case. Each rule is a predicate on packet fields, and the set of packets a rule set admits is an intersection of per-field languages over a finite alphabet of field values. Checking whether one rule set is contained in another is a language inclusion question, answered by building the product of the first with the complement of the second and testing for a reachable accepting pair. The state count is the product of the per-field state counts, which is why rule sets with many distinct port ranges and address prefixes become expensive to analyse.

Protocol validation is the second case. A protocol’s legal message sequences form a regular language, and a validator that checks several properties at once builds the product of one machine per property. The per-property machines are small; the product is not, and the engineering effort goes into keeping the properties separate until a violation is found.

In both cases the product is built lazily from the start pair, the accepting predicate is applied to the explored states, and the result is minimized before it is stored. The full cross product is never materialized, and the |Q₁| · |Q₂| bound is treated as a ceiling rather than a target.