title: "Product Construction"

Product Construction

Definition. Given DFAs $M_1 = (Q_1, \Sigma, \delta_1, q_1, F_1)$ and $M_2 = (Q_2, \Sigma, \delta_2, q_2, F_2)$, the product construction builds the DFA with state set $Q_1 \times Q_2$, start state $(q_1, q_2)$, and transition function $\delta((r,s), a) = (\delta_1(r,a), \delta_2(s,a))$.

The product machine runs both machines on the same input at once, holding one state of each, so after reading $w$ it occupies exactly the pair of states $M_1$ and $M_2$ reach on $w$. The accepting set selects the operation: $F_1 \times F_2$ gives intersection, and the pairs with at least one accepting coordinate give union. Introduced in Lecture 4 as a closure property proof, and reused in Unit 3.